一個二維偏序的問題，學過了三維偏序cdq分治之后覺得這個題非常的水。只需按一維排序之后再用樹狀數組操作即可。——by VANE

#include<bits/stdc++.h> using namespace std; const int N=5e5+5; struct qry {int x,y,id; }q[N<<2]; struct tree {int x,y; }t[N]; int s[N*5],n,m,tmp[N*5],num,vis_tim,ans[N*5]; bool cmp(qry a,qry b) {return a.x<b.x; } bool cmpp(tree a,tree b) {return a.x<b.x; } void add(int x) {for(;x<=num;x+=x&-x)s[x]++; } int query(int x) {int res=0;for(;x;x-=x&-x)res+=s[x];return res; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d%d",&t[i].x,&t[i].y);for(int i=1;i<=m;++i){int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);int pos=(i-1)*4;q[pos+1].x=xx;q[pos+1].y=yy;q[pos+1].id=pos+1;q[pos+2].x=x-1;q[pos+2].y=y-1;q[pos+2].id=pos+2;q[pos+3].x=xx;q[pos+3].y=y-1;q[pos+3].id=pos+3;q[pos+4].x=x-1;q[pos+4].y=yy;q[pos+4].id=pos+4;}for(int i=1;i<=n;++i)tmp[i]=t[i].y;for(int i=1;i<=m*4;++i)tmp[i+n]=q[i].y;sort(tmp+1,tmp+1+n+m*4);num=unique(tmp+1,tmp+1+n+4*m)-tmp-1;for(int i=1;i<=n;++i) t[i].y=lower_bound(tmp+1,tmp+1+num,t[i].y)-tmp;for(int i=1;i<=m*4;++i) q[i].y=lower_bound(tmp+1,tmp+1+num,q[i].y)-tmp;sort(q+1,q+1+4*m,cmp);sort(t+1,t+1+n,cmpp);int i=1,j=1;while(j<=4*m){int h=q[j].x;while(t[i].x<=h&&i<=n) add(t[i].y),++i;while(j<=4*m&&q[j].x==h){ans[q[j].id]+=query(q[j].y);++j;}}for(int i=1;i<=4*m;i+=4)printf("%d\n",ans[i]+ans[i+1]-ans[i+2]-ans[i+3]); }

?二維偏序用cdq我是不是有病，我就是要寫cdq 15000ms卡過去了

By：大奕哥

1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node 4 { 5 int x,y,w,id,f; 6 bool operator <(const node &b)const 7 { 8 return x==b.x?y<b.y:x<b.x; 9 } 10 }q[2500005]; 11 int cnt,maxr,tim; 12 int t[10000005],v[10000005],ans[2500005],pos[500005]; 13 inline int lowbit(int x){return x&(-x);} 14 void add(int x,int w) 15 { 16 for(;x<=maxr;x+=lowbit(x)) 17 { 18 if(v[x]!=tim) 19 { 20 v[x]=tim;t[x]=w; 21 } 22 else t[x]+=w; 23 } 24 } 25 int query(int x) 26 { 27 int an=0; 28 for(;x;x-=lowbit(x)) 29 if(v[x]==tim) 30 an+=t[x]; 31 return an; 32 } 33 void cdq(int l,int r) 34 { 35 if(l==r)return; 36 int mid=(l+r)>>1; 37 cdq(l,mid);cdq(mid+1,r); 38 sort(q+l,q+mid+1);sort(q+mid+1,q+r+1); 39 tim++; 40 int i=l,j=mid+1; 41 while(j<=r) 42 { 43 while(q[i].f==2&&i<=mid)++i; 44 while(q[j].f==1&&j<=r)++j; 45 if(q[i].x<=q[j].x&&i<=mid)add(q[i].y,q[i].w),++i; 46 else if(j<=r)ans[q[j].id]+=query(q[j].y),++j; 47 } 48 } 49 int main() 50 { 51 int n,m; 52 scanf("%d%d",&n,&m); 53 for(int i=1;i<=n;++i) 54 { 55 int x,y; 56 scanf("%d%d",&x,&y);x++;y++; 57 q[++cnt].f=1;q[cnt].x=x;q[cnt].y=y;q[cnt].w=1;q[cnt].id=cnt;maxr=max(maxr,y); 58 } 59 for(int i=1;i<=m;++i) 60 { 61 int x1,x2,y1,y2; 62 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;x2++;y1++;y2++; 63 pos[i]=cnt;maxr=max(maxr,max(y1,y2)); 64 q[++cnt].f=2;q[cnt].x=x2;q[cnt].y=y2;q[cnt].id=cnt; 65 q[++cnt].f=2;q[cnt].x=x1-1;q[cnt].y=y1-1;q[cnt].id=cnt; 66 q[++cnt].f=2;q[cnt].x=x1-1;q[cnt].y=y2;q[cnt].id=cnt; 67 q[++cnt].f=2;q[cnt].x=x2;q[cnt].y=y1-1;q[cnt].id=cnt; 68 } 69 cdq(1,cnt); 70 for(int i=1;i<=m;++i) 71 printf("%d\n",ans[pos[i]+1]+ans[pos[i]+2]-ans[pos[i]+3]-ans[pos[i]+4]); 72 return 0; 73 }

?

轉載于:https://www.cnblogs.com/nbwzyzngyl/p/8059692.html

總結

以上是生活随笔為你收集整理的BZOJ1935 园丁的烦恼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。