题目描述
很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。
有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”
“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。
“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”
“是的，显然这是一道经典的动态规划题，早在N元4002年我们就已经发现了其中的奥秘了，陛下”。
“该死的，你究竟是什么来头？”
“陛下息怒，干我们的这行经常莫名其妙地被问到和OI有关的题目，我也是为了预防万一啊！” 王者的尊严受到了伤害，这是不可容忍的。
看来一般的难题是难不倒这位园丁的，国王最后打算用车轮战来消耗他的实力： “年轻人，在我的花园里的每一棵树可以用一个整数坐标来表示，一会儿，我的骑士们会来轮番询问你某一个矩阵内有多少树，如果你不能立即答对，你就准备走人吧！”说完，国王气呼呼地先走了。
这下轮到园丁傻眼了，他没有准备过这样的问题。所幸的是，作为“全国园丁保护联盟”的会长——你，可以成为他的最后一根救命稻草。
输入输出格式
输入格式：
第一行有两个整数n，m（0≤n≤500000，1≤m≤500000）。n代表皇家花园的树木的总数，m代表骑士们询问的次数。
文件接下来的n行，每行都有两个整数xi，yi，代表第i棵树的坐标（0≤xi，yi≤10000000）。
文件的最后m行，每行都有四个整数aj，bj，cj，dj，表示第j次询问，其中所问的矩形以（aj，bj）为左下坐标，以（cj，dj）为右上坐标。
输出格式：
共输出m行，每行一个整数，即回答国王以（aj，bj）和（cj，dj）为界的矩形里有多少棵树。
输入输出样例
输入样例#1： 复制
3 1 0 0 0 1 1 0 0 0 1 1
题解
正常解法是CDQ
然而直接树状数组也能做
先把矩形给差分
先把y给离散
然后按x排序
可以保证x是单调增的
然后y用树状数组就可以了
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using std::sort; 6 using std::unique; 7 using std::lower_bound; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 char sr[1<<21],z[20];int C=-1,Z; 21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 22 inline void print(int x){ 23 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 24 while(z[++Z]=x%10+48,x/=10); 25 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 26 } 27 const int N=500005; 28 int x[N],y[N],a[N],b[N],c[N],d[N],p[N*5]; 29 int n,m,tot,cnt; 30 struct node{ 31 int x,y,id,type; 32 inline void add(int a,int b,int c=0,int d=0) 33 {x=a,y=b,id=c,type=d;} 34 inline bool operator <(const node &b)const 35 {return x<b.x||(x==b.x&&type<b.type);} 36 }q[N*5]; 37 int res[N],ans[N][5]; 38 inline void add(int x,int val){ 39 for(int i=x;i<=n;i+=i&(-i)) 40 res[i]+=val; 41 } 42 inline int query(int x){ 43 int ans=0; 44 for(int i=x;i;i-=i&(-i)) 45 ans+=res[i]; 46 return ans; 47 } 48 int main(){ 49 //freopen("testdata.in","r",stdin); 50 n=read(),m=read(); 51 for(int i=1;i<=n;++i){ 52 x[i]=read()+1,y[i]=read()+1; 53 p[++tot]=y[i]; 54 } 55 for(int i=1;i<=m;++i){ 56 a[i]=read()+1,b[i]=read()+1,c[i]=read()+1,d[i]=read()+1; 57 p[++tot]=b[i],p[++tot]=d[i]; 58 } 59 sort(p+1,p+1+tot); 60 tot=unique(p+1,p+1+tot)-p-1; 61 for(int i=1;i<=n;++i){ 62 y[i]=lower_bound(p+1,p+1+tot,y[i])-p; 63 q[++cnt].add(x[i],y[i]); 64 } 65 for(int i=1;i<=m;++i){ 66 b[i]=lower_bound(p+1,p+1+tot,b[i])-p; 67 d[i]=lower_bound(p+1,p+1+tot,d[i])-p; 68 q[++cnt].add(a[i]-1,b[i]-1,i,1),q[++cnt].add(a[i]-1,d[i],i,2); 69 q[++cnt].add(c[i],b[i]-1,i,3),q[++cnt].add(c[i],d[i],i,4); 70 } 71 sort(q+1,q+1+cnt); 72 for(int i=1;i<=cnt;++i){ 73 if(!q[i].type) add(q[i].y,1); 74 else ans[q[i].id][q[i].type]=query(q[i].y); 75 } 76 for(int i=1;i<=m;++i){ 77 int k=ans[i][4]-ans[i][3]-ans[i][2]+ans[i][1]; 78 print(k); 79 } 80 Ot(); 81 return 0; 82 }