BZOJ 1935 Tree 园丁的烦恼 CDQ分治/主席树

园丁的烦恼 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