提到cdq,就不得不提这道该死的,挨千刀的题目了。
极简题面：
给定一个二维平面，在ti时刻会在（xi，yi）放一个点，会在tj时刻查询一个方框里面的点的数量
看道题就是二维线段树乱搞啊，这么水？？？
数据范围劝退警告
单是一维都快有点吃不消了...1e6*1e6的数组？几个GB？？？
。。。
于是，伟大的CDQ分治出场了。
题面其实可以这样翻译：
按时插入点，询问小于（x，y）且时间也小于当前点的点的个数
这不就是CDQ的事吗？比模板题还要裸。。。
但是可能要差分一下（二维差分）因为统计的是点与00组成的大矩形，所以要剪去两个矩形，再加上一个小矩形，所以要统计四个点的偏序
总结一下，就是cdq。
第一维时间，第二维x，第三维y
一定要离线做
于是开始了愉快的CDQ
#include<bits/stdc++.h> using namespace std; const int maxn=505; struct node { int time,x,y,val,id; }e[maxn]; int m,cnt,t[maxn<<1],a[maxn],ans[maxn]; inline int lowbit(int x) { return x & - x ; } void add(int x,int y) { for(;x<=m;x+=lowbit(x)) { t[x]+=y; } } int ask(int x) { int res=0; for(;x;x-=lowbit(x)) { res+=t[x]; } return res; } bool cmp2(node a,node b) { if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; //else return a.time<b.time; } bool cmp(node a,node b) { return a.time<b.time; } void cdq(int l,int r) { if(l==r)return; int mid=l+r>>1; cdq(l,mid); cdq(mid+1,r); sort(e+l,e+1+r,cmp2); for(int i=l;i<=r;i++) { if(e[i].x<=mid&&e[i].id==0) add(e[i].y,e[i].val); else e[i].val+=ask(e[i].y); } for(int i=l;i<=r;i++) { if(e[i].x<=mid&&e[i].id==0) add(e[i].y,-e[i].val); } } int read() { int f=1,x=0;char s=getchar(); while(s>‘9‘||s<‘0‘){if(s==‘-‘)f=-1;s=getchar();} while(s<=‘9‘&&s>=‘0‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } int main() { read(); m=read(); int flag=read(); while(flag!=3) { if(flag==1) { int x=read()+1,y=read()+1,val=read(); e[++cnt]=(node){cnt,x,y,val,0}; } else { int x1=read(),yl=read(),x2=read()+1,y2=read()+1; e[++cnt]=(node){cnt,x1,yl,0,1};//数据结构体化 e[++cnt]=(node){cnt,x2,y2,0,1}; e[++cnt]=(node){cnt,x2,yl,0,1}; e[++cnt]=(node){cnt,x1,y2,0,1}; } flag=read(); } cdq(1,cnt);然后硬cdq就行了 sort(e+1,e+cnt+1,cmp); for(int i=1;i<=cnt;++i) { if(e[i].id==1) { printf("%d\n",e[i].val+e[i+1].val-e[i+2].val-e[i+3].val); i+=3; } } return 0; }
（完）
原文：https://www.cnblogs.com/ajmddzp/p/11300115.html