1.作用
可以用来搞一些离线的题目，用于代替复杂的数据结构入树套树。
2.做法
1.分治左边区间。
2.计算左边区间对右边区间答案的贡献。
3.分治右边区间。
4.将当前区间排序。
5.return。
3.例题
1.树状数组
单点修改区间查询。
将所有操作记录cdq分治。
每次分治时递归完了如果在左区间并且是添加操作就反手将sum+=jia，如果是询问就把ans[]+=sum。
莫得代码。
2.经典三维偏序。
设三维分别为a,b,c。
1.第一维排好序后分治，第二位用归并排序保证在这个地方询问时前面的b比当前的b小，然后第三位用树状数组压入，查询c比当前晓得。
2.只有在a在左区间时才执行添加操作，a在右区间时执行询问操作，这样就保证了询问的a永远大于加入的a。
3.总结就是第一维靠分治保证小于，第二维靠归并排序，第三位靠树状数组。
4.递归结束时要清空树状数组。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,k,shu[200005],dui[100005],cnt,daan[100005],ans[100005];
struct pigu
{
int xx,yy,zz,id;
}a[100005];
int cmp1(pigu x,pigu y)
{
if(x.xx!=y.xx)
return x.xx<y.xx;
if(x.yy!=y.yy)
return x.yy<y.yy;
if(x.zz!=y.zz)
return x.zz<y.zz;
}
int cmp2(pigu x,pigu y)
{
if(x.yy!=y.yy)
return x.yy<y.yy;
if(x.zz!=y.zz)
return x.zz<y.zz;
return x.xx<y.xx;
}
int lowbit(int x)
{
return x&(-x);
}
void cdq(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(a+l,a+r+1,cmp2);
for(int i=l;i<=r;i++)
if(a[i].xx<=mid)
{
int now=a[i].zz;
while(now<=k)
{
shu[now]++;
now+=lowbit(now);
}
}
else
{
int now=a[i].zz;
while(now)
{
daan[a[i].id]+=shu[now];
now-=lowbit(now);
}
}
for(int i=l;i<=r;i++)
if(a[i].xx<=mid)
{
int now=a[i].zz;
while(now<=k)
{
shu[now]--;
now+=lowbit(now);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].xx,&a[i].yy,&a[i].zz);
a[i].id=i;
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;)
{
int j=i+1;
while(a[i].xx==a[j].xx&&a[i].yy==a[j].yy&&a[i].zz==a[j].zz)
j++;
++cnt;
while(i<j)
{
dui[a[i].id]=a[j-1].id;
i++;
}
}
for(int i=1;i<=n;i++)
a[i].xx=i;
cdq(1,n);
for(int i=1;i<=n;i++)
{
ans[daan[dui[a[i].id]]]++;
}
for(int i=0;i<n;i++)
printf("%d
",ans[i]);
return 0;
}
/*
3 3
1 2 3
0 1 2
1 2 3
*/
3.P2163 [SHOI2007]园丁的烦恼
给出了一些点，一堆询问求一个矩形内有几个点。
一开始感觉是三维偏序，要两个log，结果发现时间没用，就成二维偏序了。
cdq分治，二维偏序，将询问拆成四个（跟矩阵前缀和差不多）就可以了。
排序时先考虑y再考虑是询问还是添加。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=5000005;
int n,m,cnt,ma,ans[N];
struct pigu
{
int pan,x,y,zai,xp;
friend bool operator <(pigu x,pigu y)
{
return x.y<=y.y;
}
}a[N],hu[N];
inline bool cmp(pigu x,pigu y)
{
return x.x==y.x?(x.y==y.y?x.pan<y.pan:x.y<y.y):x.x<y.x;
}
inline int read()
{
char c=getchar();
int x=0,f=1;
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*f;
}
inline void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int o=l,ll=l,mm=mid+1,daan=0;
while(ll<=mid&&mm<=r)
{
if(a[ll]<a[mm])
{
if(a[ll].pan==1) daan++;
hu[o++]=a[ll++];
}
else
{
if(a[mm].pan==2) ans[a[mm].zai]+=a[mm].xp*daan;
hu[o++]=a[mm++];
}
}
while(ll<=mid) hu[o++]=a[ll++];
while(mm<=r)
{
if(a[mm].pan==2) ans[a[mm].zai]+=a[mm].xp*daan;
hu[o++]=a[mm++];
}
for(int i=l;i<=r;i++) a[i]=hu[i];
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
a[++cnt].x=read()+1;a[cnt].y=read()+1;ma=max(ma,a[cnt].y);
a[cnt].pan=1;
}
for(int i=1,x,y,xx,yy;i<=m;i++)
{
x=read()+1;y=read()+1;xx=read()+1;yy=read()+1;
a[++cnt].pan=2;a[cnt].x=x-1,a[cnt].y=y-1;a[cnt].zai=i;a[cnt].xp=1;
a[++cnt].pan=2;a[cnt].x=x-1;a[cnt].y=yy;a[cnt].zai=i;a[cnt].xp=-1;
a[++cnt].pan=2;a[cnt].x=xx;a[cnt].y=y-1;a[cnt].zai=i;a[cnt].xp=-1;
a[++cnt].pan=2;a[cnt].x=xx;a[cnt].y=yy;a[cnt].zai=i;a[cnt].xp=1;
}
sort(a+1,a+cnt+1,cmp);
solve(1,cnt);
for(int i=1;i<=m;i++) cout<<ans[i]<<"
";
}
4.P4390 [BOI2007]Mokia 摩基亚
就是上一个题增加了一手修改，就再加上时间，就成了三维偏序，每个询问还是拆成四个：查询时间小于此询问，x<X,y<Y的修改。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,cnt,ma,ans[N],s[N];
struct pigu
{
int pan,x,y,zai,xp,jia;
friend bool operator <(pigu x,pigu y)
{
return x.x==y.x?(x.y==y.y?x.pan<y.pan:x.y<y.y):x.x<y.x;
}
}a[N],hu[N];
inline bool cmp(pigu x,pigu y)
{
return x.x==y.x?(x.y==y.y?x.pan<y.pan:x.y<y.y):x.x<y.x;
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void add(int x,int ad)
{
for(int i=x;i<=ma;i+=lowbit(i)) s[i]+=ad;
}
inline int query(int x)
{
int daan=0;
while(x)
{
daan+=s[x];
x-=lowbit(x);
}
return daan;
}
inline int read()
{
char c=getchar();
int x=0,f=1;
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*f;
}
inline void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int o=l,ll=l,mm=mid+1;
while(ll<=mid&&mm<=r)
{
if(a[ll]<a[mm])
{
if(a[ll].pan==1) add(a[ll].y,a[ll].jia);
hu[o++]=a[ll++];
}
else
{
if(a[mm].pan==2) ans[a[mm].zai]+=a[mm].xp*query(a[mm].y);
hu[o++]=a[mm++];
}
}
while(ll<=mid) add(a[ll].y,a[ll].jia),hu[o++]=a[ll++];
while(mm<=r)
{
if(a[mm].pan==2) ans[a[mm].zai]+=a[mm].xp*query(a[mm].y);
hu[o++]=a[mm++];
}
for(int i=l;i<=mid;i++) if(a[i].pan==1) add(a[i].y,-a[i].jia);
for(int i=l;i<=r;i++) a[i]=hu[i];
}
int main()
{
int xipan=read(),gu=0;
while(xipan!=3)
{
int x,y,xx,yy;
if(xipan==0) ma=read()+1;
if(xipan==1)
{
a[++cnt].x=read()+1;a[cnt].pan=1;a[cnt].y=read()+1;a[cnt].jia=read();
}
if(xipan==2)
{
x=read()+1;y=read()+1;xx=read()+1;yy=read()+1;
a[++cnt].pan=2;a[cnt].x=x-1,a[cnt].y=y-1;a[cnt].zai=++gu;a[cnt].xp=1;
a[++cnt].pan=2;a[cnt].x=x-1;a[cnt].y=yy;a[cnt].zai=gu;a[cnt].xp=-1;
a[++cnt].pan=2;a[cnt].x=xx;a[cnt].y=y-1;a[cnt].zai=gu;a[cnt].xp=-1;
a[++cnt].pan=2;a[cnt].x=xx;a[cnt].y=yy;a[cnt].zai=gu;a[cnt].xp=1;
}
if(xipan==3) break;
xipan=read();
}
solve(1,cnt);
for(int i=1;i<=gu;i++) cout<<ans[i]<<"
";
}
5.P4027 [NOI2007]货币兑换
首先斜率优化那个样子搞一哈虱子，然后发现x不递增，斜率不递增，就可以用splay动态维护凸包，二分查找最近的斜率。
还可以cdq分治一波，先总体全部按照k排序，左区间搞一手斜率单调递减，右区间由于k拍好了序，就可以直接在左边维护好的东西头查询。
注意每次操作前要先把整个区间按照时间排序拍好，递归完了就可以不需要管时间了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-7;
const double inf=1e10;
int n;
double f[N];
struct pigu
{
double x,y,a,b,r,k;
int id;
}wen[N],hu[N],hu2[N];
inline int read()
{
char c=getchar();
int x=0,f=1;
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*f;
}
inline bool cmp(pigu x,pigu y)
{
return x.k<y.k;
}
inline double xl(int x,int y)
{
if(fabs(wen[x].x-wen[y].x)<=eps) return inf;
return (wen[x].y-wen[y].y)/(wen[x].x-wen[y].x);
}
int st[N];
inline void merge(int l,int r)
{
int mid=(l+r)>>1;
int t1=l,t2=mid+1;
for(int i=l;i<=r;++i)
if(t1<=mid&&(t2>r||wen[t1].x<wen[t2].x+eps)) hu[i]=wen[t1++];
else hu[i]=wen[t2++];
for(int i=l;i<=r;++i) wen[i]=hu[i];
}
inline void solve(int l,int r)
{
if(l==r)
{
f[l]=max(f[l],f[l-1]);
wen[l].y=f[l]/(wen[l].a*wen[l].r+wen[l].b);
wen[l].x=wen[l].y*wen[l].r;
return;
}
int mid=(l+r)>>1,ll=l-1,mm=mid;
for(int i=l;i<=r;i++)
{
if(wen[i].id<=mid) hu[++ll]=wen[i];
else hu[++mm]=wen[i];
}
for(int i=l;i<=r;i++) wen[i]=hu[i];
solve(l,mid);
int top=0;
for(int i=l;i<=mid;i++)
{
while(top>=2&&xl(st[top],st[top-1])<xl(i,st[top])+eps) top--;
st[++top]=i;
}
for(int i=mid+1;i<=r;i++)
{
while(top>1&&xl(st[top],st[top-1])<wen[i].k+eps) top--;
f[wen[i].id]=max(f[wen[i].id],wen[i].a*wen[st[top]].x+wen[i].b*wen[st[top]].y);
}
solve(mid+1,r);merge(l,r);
}
int main()
{
n=read();scanf("%lf",&f[0]);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&wen[i].a,&wen[i].b,&wen[i].r);
wen[i].k=-wen[i].a/wen[i].b;wen[i].id=i;
}
sort(wen+1,wen+n+1,cmp);
solve(1,n);
printf("%.3lf",f[n]);
}