CDQ分治其实就是一个离线分治算法。
对于每一个询问,只需考虑原有的点,以及在其之前的修改操作对其造成的影响。
简单来讲,对于第$k$项询问,只需统计$1\sim k-1$的修改操作(把原有点也看作修改)就行了。
如果每一次都仅对一个询问进行统计答案,过于浪费,因此可以整体分治询问统计答案。
具体分治过程是这样的:
- 设$mid=l+r>>1$,递归计算$solve(l,mid),solve(mid+1,r)$
- 计算第$l\sim mid$项操作中的所有“修改”对第$mid+1\sim r$操作中所有“查询”造成的影响。
正确性证明:
对于第$k$项询问,若$k\le mid$,那么$solve(l,mid)$就已经解决了第$l,k-1$项操作中的“修改”对它的影响。
若$k>mid$,那么$solve(l,r)$解决第$l,mid$项修改,$solve(mid+1,r)$解决$mid+1,r$,证毕。
其实这道题是一道三维偏序问题。
简要题意就是,统计对于$\forall i$,询问$a_j<=a_i,b_j<=b_i,c_j<=c_i$的$j$的个数。
转化为本题题意:
- 第一维即为时间,第二维即为$x$坐标,第三维即为$y$坐标
通常来讲,第一维需要整体排序,第二维需要在分治时,分$l,mid$,$mid+1,r$两端排序,第三维通过数据结构维护。
对于本题来讲,以左下为例:
对于第$k$个询问询问$x,y,z$,统计前$k-1$项的修改操作对其答案的贡献,$ans=\min (x+y)-(x_i+y_i)$。
左上,右下,右上可自行推导。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=5e5+10;
const int inf=0xcfcfcfcf;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int n,m,t,tot;
struct node{int x,y,z;bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}}a[N<<1],b[N<<1];
int c[N<<1],ans[N<<1],mx;
int ask(int x){int ans=inf;for(;x;x-=x&-x)ans=max(ans,c[x]);return ans;}
void add(int x,int k){for(;x<mx;x+=x&-x)c[x]=max(c[x],k);}
void calc(int l,int r,int d,int dx,int dy)
{
for(int i=l;i!=r;i+=d)
{
int y=(dy==1?b[i].y:mx-b[i].y);
//mx-b[i].y是b[i].y水平平移的结果,因为树状数组只能统计1~b[i].y,若统计上方的点时,得处理成-b[i].y,才能统计上方的点,为了保证正数,因此水平平移。
int temp=b[i].x*dx+b[i].y*dy;
if(a[b[i].z].z==1)add(y,temp);
else ans[b[i].z]=min(ans[b[i].z],abs(temp-ask(y)));
}
for(int i=l;i!=r;i+=d)//还原
if(a[b[i].z].z==1)
{
int y=(dy==1?b[i].y:mx-b[i].y);
for(;y<mx;y+=y&-y)c[y]=inf;
}
}
void cdqdiv(int l,int r)
{
int mid=l+r>>1;
if(l<mid)cdqdiv(l,mid);
if(r>mid+1)cdqdiv(mid+1,r);
int len=0;
for(int i=l;i<=r;i++)
if((i<=mid&&a[i].z==1)||(i>mid&&a[i].z==2))
b[++len]=a[i],b[len].z=i;//处理第一维时间
sort(b+1,b+len+1);//处理第二维x
calc(1,len+1,1,1,1),calc(1,len+1,1,1,-1);//处理第三维y
calc(len,0,-1,-1,1),calc(len,0,-1,-1,-1);
}
int main()
{
int n,m;qr(n),qr(m);memset(c,0xcf,sizeof(c));mx=inf;memset(ans,0x3f,sizeof(ans));
for(int i=1;i<=n;i++)qr(a[i].x),qr(a[i].y),a[i].z=1,++a[i].y;
for(int i=n+1;i<=n+m;i++)qr(a[i].z),qr(a[i].x),qr(a[i].y),++a[i].y;
for(int i=1;i<=n+m;i++)mx=max(mx,a[i].y);++mx;
cdqdiv(1,n+m);
for(int i=n+1;i<=n+m;i++)if(a[i].z==2)qw(ans[i]),puts("");
return 0;
}
最后一次更新于2019-10-12
0 条评论