CH4701 天使玩偶

题意

描述

题目PDF

样例输入

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

样例输出

1
2

来源

石家庄二中Violet 3杯省选模拟赛

分析

参照Dilthey的题解。(话说怎么会有人这么闲,把书上的内容打了一遍。)

关于CDQ分治(参考李煜东《算法竞赛进阶指南》):

对于一系列操作,其中的任何一个询问操作,其结果必然等价于:初始值 + 此前所有的修改操作产生的影响。

假设共有 \(m\) 次操作,对于任意的满足 \(1 \le l \le r \le m\) 的正整数 \(l,r\),定义 \(solve(l,r)\) 为:对于任意的正整数 \(k \in [l,r]\),若第 \(k\) 次操作为询问操作,则计算第 \(l \sim k-1\) 次操作中的修改操作对第 \(k\) 次查询的影响。\(solve(l,r)\) 可以通过分治来计算:

  1. 设 \(mid = (l+r)>>1\),递归计算 \(solve(l,mid)\) 和 \(solve(mid+1,r)\)。
  2. 计算第 \(l \sim mid\) 次操作中所有修改操作对第 \(mid+1 \sim r\) 次操作中所有询问操作的影响。

同时,根据 \(solve(l,r)\) 的定义,显然 \(solve(1,m)\) 即为原始问题(不考虑初始值的情况下),而当 \(l=r\) 时 \(solve(l,r)\) 显然不需要进行任何计算。

第 2 部分的操作,其实是一个静态问题,因为修改和询问是完全被前后分开的。类比于经典分治算法归并排序,我们只要让计算第 2 部分的时间复杂度只和 \(r-l\) 线性相关,就可以使得总的时间复杂度为 \(O(m \log m)\)。

这种离线分治算法是基于时间顺序对操作序列进行分治的,因此称为基于时间的分治算法,或者更加广泛的名称CDQ分治。

题解:

这个题,剥离题目背景,无非就是在二维平面上,在若干时刻放置一个点在某个位置,同时在若干时刻查询某个位置与其最近邻的距离。

自然而然就会想起KDTree,不过我还不会带修改的KDTree怎么办,那不妨考虑一下一个简单的问题,假设没有修改操作,只在一开始就给定你平面上若干个点,后续全部都是查询操作。

即:给定平面上 \(n\) 个点 \((x_i,y_i)\),有 \(m\) 次查询操作,每次询问距离 \((x,y)\) 位置的最近的点有多远(KDTree板子题)。显然,答案就是 \(\min_{1 \le i \le n}\{ |x - x_i| + |y - y_i| \}\)。

方便起见,为了去掉绝对值符号,不妨把询问变成询问四个方向(第 \(1,2,3,4\) 象限方向)上距离最近的点。那么,以第三象限方向上的询问为例,其答案就变成:

\(\min_{1 \le i \le n}\{ x - x_i + y - y_i \} = (x+y) - \max_{1 \le i \le n}\{x_i + y_i\}\)

其中,\(\forall x_i,y_i\) 满足 \(x_i \le x\) 且 \(y_i \le y\)。

此时,可以考虑树状数组优化时间复杂度,先把所有平面上的点和询问中的位置按横坐标从小到大排个序,然后依次进行扫描。

若扫描到一个点 \((x_i,y_i)\),则在树状数组中把第 \(y_i\) 个位置上的值和 \(x_i+y_i\) 取较大值。
若扫描到一个询问的位置 \((x,y)\),则在树状数组中查询区间 \([0,y]\) 上的最大值。
显然,按照横坐标从小到大扫描,使得每次询问时,树状数组中存储的值都是 \(x\) 值不大于当前位置的点,而在区间 \([0,y]\) 的查询就迫使所有被考虑的点的 \(y\) 值都是不超过当前位置的。

时间复杂度 \(O((n+m)\log(n+m))\)。

然后,我们回到原来的问题,对于原问题,我们使用CDQ分治,那么需要考虑的问题就变成了 \(solve(l,r)\) 中,如何计算第 \(l \sim mid\) 次操作中所有修改操作对第 \(mid+1 \sim r\) 次操作中所有询问操作的影响。换句话说,如何计算第 \(l \sim mid\) 次操作中所有添加进来的点,对第 \(mid+1 \sim r\) 次操作中所有询问的影响。这样一看,这不就是上面讲到的简化版问题吗。

当然,为了保证每次计算静态问题的时间复杂度仅和 \(r-l\) 相关,不能每次都建立一个新的树状数组,必须在每次计算 \(solve(l,r)\) 后,把对树状数组的修改都撤销掉。也就是说,要保证对于每个 \(solve(l,r)\),在进入和离开函数时,树状数组都是空的。

这样一来,不妨把初始的 \(n\) 个点也看做修改操作,对于总的 \(n+m\) 次操作,总时间复杂度就是 \(O((n+m) \log^2 (n+m))\)。

代码

体验了数组卡着开的乐趣。

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=1e6+1,INF=0x3f3f3f3f;
int n,m,ans[N],maxy=-INF,c[N];
struct P{
    int t,x,y;
    bool operator<(co P&a)co {return x<a.x;}
}a[N],b[N];
void add(int y,int num){
    for(;y<maxy;y+=y&-y) c[y]=max(c[y],num);
}
int ask(int y){
    int ans=-INF;
    for(;y;y-=y&-y) ans=max(ans,c[y]);
    return ans;
}
void re(int y){
    for(;y<maxy;y+=y&-y) c[y]=-INF;
}
void work(int st,int ed,int w,int dx,int dy){
    for(int i=st;i!=ed;i+=w){
        int y=dy==1?b[i].y:maxy-b[i].y;
        int num=dx*b[i].x+dy*b[i].y;
        if(a[b[i].t].t==1) add(y,num);
        else ans[b[i].t]=min(ans[b[i].t],abs(num-ask(y)));
    }
    for(int i=st;i!=ed;i+=w)
        if(a[b[i].t].t==1) re(dy==1?b[i].y:maxy-b[i].y);
}
void CDQ(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    int tot=0;
    for(int i=l;i<=r;++i)
        if(i<=mid&&a[i].t==1||i>mid&&a[i].t==2)
            b[++tot]=a[i],b[tot].t=i;
    sort(b+1,b+tot+1);
    work(1,tot+1,1,1,1);
    work(1,tot+1,1,1,-1);
    work(tot,0,-1,-1,-1);
    work(tot,0,-1,-1,1);
}
int main(){
//  freopen("CH4701.in","r",stdin),freopen("CH4701.out","w",stdout);
    read(n),read(m);
    for(int i=1;i<=n;++i) read(a[i].x),maxy=max(maxy,read(a[i].y)),a[i].t=1;
    for(int i=1;i<=m;++i) read(a[i+n].t),read(a[i+n].x),maxy=max(maxy,read(a[i+n].y));
    ++maxy;
    memset(ans,0x3f,sizeof ans);
    memset(c,0xcf,sizeof c);
    CDQ(1,n+m);
    for(int i=n+1;i<=n+m;++i)
        if(a[i].t==2) printf("%d\n",ans[i]);
    return 0;
}
上一篇:Array GCD CodeForces - 624D (数学,gcd)


下一篇:UVa839