园丁的烦恼 CDQ分治/主席树"/>
BZOJ 1935 Tree 园丁的烦恼 CDQ分治/主席树
CDQ分治版本
我们把询问拆成四个前缀和,也就是二维前缀和的表达式,
我们把所有操作放入一个序列中
操作1代表在x,y出现一个树
操作2代表加上在x,y内部树的个数
操作3代表减去在x,y内部树的个数
我们对X进行归并排序,并用CDQ计算机左区间对右区间的影响
由于CDQ分治的特性,我们已经求得了[L,MID]之间答案 以及 [MID+1,R]之间答案
那么[L,MID] 对[MID+1,R] 的影响是什么呢?
很简单,对于L<=i<=MID , MID+1<=j<=R 来说
i 对 j 影响是当 a[i]的操作是1,那么会对 j 内的求和操作产生影响。
但是i的求和操作实际上已经进行了不会对j内产生影响,并且j内部的操作1,对j的求和操作也没有影响,而且这一部分实际上是已经计算过的了。
因为我们在计算两个区间的相互影响的时候,就是维护左区间的操作1,以及右区间的求和操作(操作2,操作3)。
#include<bits/stdc++.h> using namespace std; const int maxx = 500005; const int maxn =10000005; struct node{int x,y,op,id; }a[maxx*5],b[maxx*5]; int num[maxx]; int sum[maxn]; int mx,tot; int lowbit(int x){return x&(-x); } void add(int x,int w){for (int i=x;i<=mx;i+=lowbit(i)){sum[i]+=w;} } int query(int x){int ans=0;for (int i=x;i;i-=lowbit(i)){ans+=sum[i];}return ans; } void clear_bit(int x){for (int i=x;i<=mx;i+=lowbit(i)){if(sum[i]==0)break;sum[i]=0;} } void cdq(int l,int r){if (l==r){return;}int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);int i=l,j=mid+1,k=l;///归并排序while(i<=mid && j<=r){if (a[i].x<=a[j].x){///如果当前左边的值小于右边,那么对于操作2,3来说,实际上已经是计算过了,并且这个区间对右边区间只有操作1有影响if(a[i].op==1){add(a[i].y,1);}///把a[i]加入b[i]中排序b[k++]=a[i++];}else {///如果是操作2的话,我们只需要查询比a[j].y小的个数即可if(a[j].op==2){num[a[j].id]+=query(a[j].y);}else if(a[j].op==3){///操作3的话,我们需要减去比a[j].y,num[a[j].id]-=query(a[j].y);}b[k++]=a[j++];}}while(i<=mid){if(a[i].op==1)add(a[i].y,1);b[k++]=a[i++];}while(j<=r){if(a[j].op==2)num[a[j].id]+=query(a[j].y);else if(a[j].op==3)num[a[j].id]-=query(a[j].y);b[k++]=a[j++];}for (int i=l;i<=r;i++){clear_bit(a[i].y);a[i]=b[i];} } int main(){int n,m,lx,ly,rx,ry;scanf("%d%d",&n,&m);tot=0;mx=0;int x,y;memset(num,0,sizeof(num));///左标+1防止树状数组取到0for (int i=1;i<=n;i++){scanf("%d%d",&x,&y);x++;y++;tot++;a[tot].x=x;a[tot].y=y;a[tot].op=1;}for(int i=1;i<=m;i++){scanf("%d%d%d%d",&lx,&ly,&rx,&ry);lx++;ly++;rx++;ry++;///二维前缀和a[++tot]={lx-1,ly-1,2,i};a[++tot]={rx,ry,2,i};a[++tot]={lx-1,ry,3,i};a[++tot]={rx,ly-1,3,i};mx=max(mx,ly);mx=max(mx,ry);}cdq(1,tot);for (int i=1;i<=m;i++){printf("%d\n",num[i]);}return 0; }
当然这道题也是可以用主席树写的。。。嘿嘿
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #define LL long long using namespace std; const int maxx = 5e5+10; struct node{int l,r;LL w; }tree[maxx*40]; int root[maxx]; struct Node{int x,y;LL w;bool operator < (const Node & s)const{return x<s.x;} }point[maxx]; vector<int>vx; vector<int>vy; LL n; int cnt; LL get_val(LL x,LL y){LL k=min(x,min(n-x+1,min(y,n-y+1)));LL minn=k;k--;LL in=n-2*k;LL out=n*n-in*in;if (x==n-minn+1){return out+n-k-y+1;}else if (y==minn){return out+in+n-k-x;}else if (x==minn){return out+in*2-2+y-k;}else {return out+in*3-3+x-k;} } void inserts(int l,int r,int pre,int &now,int pos,LL w){now=++cnt;tree[now]=tree[pre];tree[now].w+=w;if(l==r){return ;}int mid=(l+r)>>1;if(pos<=mid)inserts(l,mid,tree[pre].l,tree[now].l,pos,w);else inserts(mid+1,r,tree[pre].r,tree[now].r,pos,w); } LL query(int L,int R,int l,int r,int ql,int qr){//区间查询if(ql<=l && r<=qr){return tree[R].w-tree[L].w;}int mid=(l+r)>>1;LL ans=0;if (qr<=mid){return query(tree[L].l,tree[R].l,l,mid,ql,qr);}else if (ql>mid){return query(tree[L].r,tree[R].r,mid+1,r,ql,qr);}else {return query(tree[L].l,tree[R].l,l,mid,ql,qr)+query(tree[L].r,tree[R].r,mid+1,r,ql,qr);} } int main(){int m,p;cnt=0;memset(root,0,sizeof(root));memset(tree,0,sizeof(tree));scanf("%d%d",&m,&p);vx.clear();vy.clear();for(int i=1;i<=m;i++){scanf("%d%d",&point[i].x,&point[i].y);point[i].w=1;vx.push_back(point[i].x);vy.push_back(point[i].y);}sort(point+1,point+1+m);sort(vx.begin(),vx.end());sort(vy.begin(),vy.end());vy.erase(unique(vy.begin(),vy.end()),vy.end());int sz=vy.size();for (int i=1;i<=m;i++){int posy=lower_bound(vy.begin(),vy.end(),point[i].y)-vy.begin()+1;inserts(1,sz,root[i-1],root[i],posy,point[i].w);}while(p--){int lx,rx,ly,ry;scanf("%d%d%d%d",&lx,&ly,&rx,&ry);lx=lower_bound(vx.begin(),vx.end(),lx)-vx.begin()+1;rx=upper_bound(vx.begin(),vx.end(),rx)-vx.begin();ly=lower_bound(vy.begin(),vy.end(),ly)-vy.begin()+1;ry=upper_bound(vy.begin(),vy.end(),ry)-vy.begin();if (lx>rx || ly>ry){printf("0\n");continue;}printf("%lld\n",query(root[lx-1],root[rx],1,sz,ly,ry));}return 0; } /**/
转载于:.html
更多推荐
BZOJ 1935 Tree 园丁的烦恼 CDQ分治/主席树
发布评论