首页 > 其他 > 详细

[BOI2007]Mokia 摩基亚

时间:2019-07-13 19:28:35      阅读:89      评论:0      收藏:0      [点我收藏+]

我才不会告诉你我cmp写错了,然后调了一年

CDQ分治模板题

一维时间,二三维x,y坐标

避免树状数组下标出现0炸掉,把跟长度有关的都+1

答案用容斥原理即可(类似于二维前缀和?)

 

 1 //LevenKoko
 2 #include<bits/stdc++.h>
 3 #define lowbit(x) (x&(-x))
 4 using namespace std;
 5 inline int read(){
 6     int ans=0,f=1;char chr=getchar();
 7     while(!isdigit(chr)){if(chr==-)f=-1;chr=getchar();}
 8     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 9     return ans*f;
10 }const int M=2e6+5,N=2e5+5;
11 int opt,s[M],n,t,x,y,z,xx,yy;
12 struct P{int t,x,y,cnt,id;}a[N];
13 bool cmp1(P x,P y){if(x.x==y.x) return x.y<y.y;return x.x<y.x;}
14 bool cmp2(P x,P y){return x.t<y.t;}
15 inline void Add(int x,int z){for(;x<=n;x+=lowbit(x)) s[x]+=z;}
16 inline int  Ask(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=s[x];return ans;}
17 inline void Plu(int x,int y){a[++t]=(P){t,x,y,0,1};}
18 inline void Init(){
19     read(),n=read()+1;
20     while(opt=read()){
21         if(opt==1)x=read()+1,y=read()+1,z=read(),a[++t]=(P){t,x,y,z,0};
22         if(opt==2)x=read(),y=read(),xx=read()+1,yy=read()+1,Plu(x,y),Plu(xx,yy),Plu(xx,y),Plu(x,yy);
23         if(opt==3) break;
24     }
25 }
26 inline void Solve(int l,int r){
27     if(l==r) return;
28     int mid=l+r>>1;
29     Solve(l,mid),Solve(mid+1,r);
30     sort(a+l,a+mid+1,cmp1),sort(a+mid+1,a+r+1,cmp1);
31     int i=l,j=mid+1;
32     for(;j<=r;j++){
33         while(a[i].x<=a[j].x&&i<=mid){
34             if(a[i].id==0) Add(a[i].y,a[i].cnt);
35             i++;
36         }if(a[j].id==1) a[j].cnt+=Ask(a[j].y);
37     }
38     for(j=l;j<i;j++) if(a[j].id==0)Add(a[j].y,-a[j].cnt);
39 }
40 inline void Get(){
41     sort(a+1,a+t+1,cmp2);
42     for(int i=1;i<=t;i++)
43         if(a[i].id==1)
44             printf("%d\n",a[i].cnt+a[i+1].cnt-a[i+2].cnt-a[i+3].cnt),i+=3;
45 }
46 int main(){
47     return Init(),Solve(1,t),Get(),0;
48 }

 

 

 

 

[BOI2007]Mokia 摩基亚

原文:https://www.cnblogs.com/zhenglw/p/11181658.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!