基于时间的分治算法（cdq分治）

ID: 360

客观题

尝试: 3

已通过: 2

难度: 10

上传者:

boya

对于操作序列中的每个“查询”，计算其结果等价于计算“初始”以及“之前的所有修改”对查询造成的影响。

设共有 $M$ 项操作， $\forall l,r \in[1,M]$ , $l\le r$ , 定义 $solve(l,r)$ 为： $\forall k \in[l,r]$ , 若第 $k$ 项操作是“查询” ，则计算第 $l \sim k-1$ 项操作中的“修改” 对它造成的影响。

计算方法如下：

1.设 $mid=\frac{l+r}{2}$ ，递归计算 $solve(l,mid)$
2.递归计算 $solve(mid+1,r)$
3.计算第 $l\sim mid$ 项操作中的所有“修改”对第 $mid+1\sim r$ 项操作中所有“查询”造成的影响

上述离线方法为什么正确？

证明：

设第 $k$ 项操作是“查询”。根据定义，若 $k\le mid$ ,则 $solve(l,mid)$ 已经计算了第 $l \sim k-1$ 项操作中“修改”对它的影响。若 $k>mid$ ,则 $solve(mid+1,r)$ 计算了第 $mid+1 \sim k-1$ 项操作中的“修改”对它的影响，再加上第 3 部分的计算，即得到了第 $l \sim k-1$ 项操作中的“修改” 对它的影响。

常见情况时间复杂度：

$T(n)=2T(n/2)+O(n) \longrightarrow O(n\log{n})$

$T(n)=2T(n/2)+O(n\log{n})\longrightarrow O(n\log^2{n})$

例 P3810三维偏序

分析：

先按照一维属性排序去重
1. 假设三维分别是 x,y,z ,先按 x 排序。
2. 然后去掉重复元素，记录每个元素出现的次数 cnt
CDQ分治：类似于归并排序的思想，先按第一维属性划分为前一半和后一半，回溯后计算前一半修改对后一半查询的影响。
1. 分治后每次将前一半、后一半分别按 y 排序。虽然 x 的顺序被打乱了，但前一半的 x 还是都小于后一半的，所以只计算前一半对后一半的偏序关系，是不会受到 x 影响的。
2. 用双指针 i,j 来指向前一半和后一半，每次将 j 后移一位时，若 y[i]<=y[j] 则不断后移 $i$ ,并不断将 z[i] 加入树状数组。然后再查询树状数组中有多少个数 <=z[j] ,即 <=e[j] 的排序数量。
3. 最后要清空树状数组。

参考代码：

  #include<bits/stdc++.h>
  using namespace std;
  const int N=1e5+10;
  struct node{
  	int a,b,c,cnt,val;
  }e[N],t[N];
  bool operator ==(node x,node y)
  {
  	if(x.a==y.a&&x.b==y.b&&x.c==y.c)return true;
  	return false;
  }
  int n,K,f[N<<1],num,ans[N];
  
  void add(int x,int d)
  {
  	for(int i=x;i<=K;i+=i&(-i))
  		f[i]+=d;
  }
  int query(int x)
  {
  	int ret=0;
  	for(int i=x;i;i-=i&(-i))
  		ret+=f[i];
  	return ret;
  }
  
  bool cmpa(node x,node y)
  {
  	if(x.a!=y.a)return x.a<y.a;
  	if(x.b!=y.b)return x.b<y.b;
  	return x.c<y.c;
  }
  
  void cdq(int l,int r)
  {
  	if(l==r)return;
  	int mid=(l+r)>>1;
  	cdq(l,mid);       //第二维b已经有序 
  	cdq(mid+1,r);     //第二维b已经有序 
  	int i=l,j=mid+1,p=l;  //归并，同时维护c的影响 双指针 
  	while(i<=mid && j<=r)
  		if(e[i].b<=e[j].b)add(e[i].c,e[i].cnt),t[p++]=e[i++];
  		else  e[j].val+=query(e[j].c),t[p++]=e[j++];
  	
  	while(i<=mid)add(e[i].c,e[i].cnt),t[p++]=e[i++];
  	while(j<=r)e[j].val+=query(e[j].c),t[p++]=e[j++];
  	
  	for(int i=l;i<=mid;i++)add(e[i].c,-e[i].cnt);
  	
  	for(int i=l;i<=r;i++)e[i]=t[i];
  }
  int main()
  {
  	ios::sync_with_stdio(false);
  	cin>>n>>K;
  	for(int i=1;i<=n;i++)
  	{
  		cin>>e[i].a>>e[i].b>>e[i].c;
  		e[i].cnt=1;
  	}
  	sort(e+1,e+n+1,cmpa);
  	num=1;
  	for(int i=2;i<=n;i++)
  		if(e[i]==e[num])e[num].cnt++;
  		else e[++num]=e[i];
  	
  	/*for(int i=1;i<=num;i++)
  		cout<<i<<":"<<e[i].a<<" "<<e[i].b<<" "<<e[i].c<<" "<<e[i].cnt<<endl;
  	*/
  	cdq(1,num);
  	for(int i=1;i<=num;i++)
  		ans[e[i].val+e[i].cnt-1]+=e[i].cnt;
  	for(int i=0;i<n;i++)
  		cout<<ans[i]<<endl;
  
  	return 0;
  }

例 P4169 [Violet] 天使玩偶/SJY摆棋子

本题有若干操作，动态插入一些点，询问某个点距离最近的点的曼哈顿距离。

暂时忽略掉插入新点操作，查询 $(x,y)$ 最近的点的距离，答案就是： $min\{|x-x_i|+|y-y_i|\}$ , 为了去掉绝对值，我们将询问分成 $4$ 类，分别询问左下、左上、右下、右上方向上距离最近的点的距离，保留最小的就是答案。

左下： $min\{(x-x_i)+(y-y_i)\}=(x+y)-max\{x_i+y_i\}$
左上： $min\{(x-x_i)+(y_i-y)\}=(x-y)-max\{x_i-y_i\}$
右下： $min\{(x_i-x)+(y-y_i)\}=(-x+y)-max\{-x_i+y_i\}$
右上： $min\{(x_i-x)+(y_i-y)\}=(-x-y)-max\{-x_i-y_i\}$

我们可以将 $n$ 个点的坐标和 $m$ 个询问的坐标按照横坐标从小到大排序。然后依次扫描。

对于左下方来说：

若扫描到一个点 $(x_i,y_i)$ ,则在树状数组第 $y_i$ 个位置上的值与 $x_i+y_i$ 取最大，同时维护前缀最大。
如果扫描到了一个查询 $(x,y)$ ，则在树状数组，则在树状数组(或线段树)中查询 $[1,y]$ 的最大 $val$ ，该询问就是 $x+y-val$ .

上面的做法，排序保证了 $x_i<x$ 的条件，树状数组控制 $y_i<y$ 的条件并维护了 $x_i+y_i$ 的最大值。

对于左上、右上和左下与上述方法类似，例如左上方，还是按照横坐标排序，这时应该是 $x_i≤x,10^6−y_i≤10^6−y$ ，因此树状数组改成维护 $x_i−y_i$ 的最大值，修改时的位置变为 $10^6−yi+1$ ，查询时的前缀变为 $[1,10^6-y_i+1]$ ，剩下两个方向可自行推导。

到这里我们再加上加入操作，除了查询还可能在平面中添加点。有查询和插入操作的动态问题，这就可以用 CDQ 分治分成若干个静态小问题来解决。

那么我们每次递归完左、右区间之后还需要处理左区间修改对右区间查询的影响。可以把第 $l \sim mid$ 项操作中增加的点依次加入一个初始为空的平面，再考虑第 $mid+1∼r$ 项操作中的查询，找到平面上距离最近的点来更新答案，可以用和上面一样的做法。

注意！为了保证每次的时间复杂度之和当前递归的区间内部相关，因此每次不能建立一个新的树状数组，必须在处理完每个区间后再将对树状数组的修改依次还原，保证每次进入和离开时，树状数组都是空的，可以复用。这样整个算法的时间复杂度为 $O((n + m) \log_2^2(n + m))$

注意！ 本题会卡常，需要在 CDQ 分治时进行一些优化，如果区间中只存在添加操作，不存在查询操作，那么不需要处理左区间的修改操作对右区间的查询操作的影响。这是一步效果非常明显的优化(不加这步就只能吸氧了)

参考代码：

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int N=1e6+10,INF=0x3f3f3f3f;
  struct node{
      int x,y,z;
      bool operator<(node t)const{
          return x<t.x;  //按照x从小到大排序
      };
  };
  node a[N],b[N];
  int n,m,tr[N],ans[N],maxy;  //tr[]树状数组维护前缀最大值
  
  void insert(int x,int d)
  {
      for(int i=x;i<=maxy;i+=i&(-i))tr[i]=max(tr[i],d);
  }
  int query(int x)
  {
      int ret=-INF;
      for(int i=x;i;i-=(i&(-i)))ret=max(ret,tr[i]);
      return ret;
  }
  void work(int st,int ed,int step,int dx,int dy)
  {
      for(int i=st;i!=ed;i+=step)
      {
          int y;
          if(dy==1)y=b[i].y;
          else y=maxy-b[i].y+1;
  
          int dist=dx* b[i].x +dy* b[i].y;
          if(a[b[i].z].z==1) insert(y,dist);   //插入操作 树状数组 y 位置维护 dx*x+dy*y 的最大值
          else ans[b[i].z]=min(ans[b[i].z],dist-query(y));
      }
      //还原
      for(int i=st;i!=ed;i+=step)
      {
          int y;
          if(dy==1)y=b[i].y;
          else y=maxy-b[i].y+1;
          
          if(a[b[i].z].z==1)
          {
              for(int j=y;j<=maxy;j+=j&(-j))
              {
                  if(tr[j]==-INF)break;
                  tr[j]=-INF;
              }
          }
      }
  }
  
  void cdq(int l,int r)
  {
      if(l==r)return;
      int mid=l+r>>1;
      cdq(l,mid); 
      cdq(mid+1,r);
  
      if(r>n)  //当r<=n 只有插入操作，没有询问，对询问不构成修改
      {
          int cnt=0;
          for(int i=l;i<=r;i++)
              if((i<=mid && a[i].z==1)||(i>mid && a[i].z==2))
                  b[++cnt]=a[i],b[cnt].z=i;
  
          sort(b+1,b+cnt+1);  //按照横坐标排序
  
          work(1,cnt+1,1,1,1);  //左下 xi<x yi<y, ans=x+y-max{xi+yi};
          work(1,cnt+1,1,1,-1);  //左上 xi<x yi>y, ans=x-y-max{xi-yi};
          
          work(cnt,0,-1,-1,-1);   //右上 xi>x yi>y, ans=-x-y-max{-xi-yi};
          work(cnt,0,-1,-1,1);   //右下 xi>x yi<y,ans=(-x+y)-max{-xi+yi};
      }
  }
  int main()
  {
      ios::sync_with_stdio(false); cin.tie(0);
      cin>>n>>m;
      for(int i=1;i<=n;i++)
      {
          cin>>a[i].x>>a[i].y;
          a[i].z=1;
          a[i].y++;  //使得y的值域大于0
      }
      m+=n;
      for(int i=n+1;i<=m;i++)
      {
          cin>>a[i].z>>a[i].x>>a[i].y;
          a[i].y++;
      }
  
      for(int i=1;i<=m;i++)maxy=max(maxy,a[i].y);
  
      for(int i=0;i<N;i++)tr[i]=-INF;  //树状数组初始化为负无穷
      for(int i=0;i<N;i++)ans[i]=INF; //ans答案保留最小，因此初始化为正无穷
  
      cdq(1,m);
  
      for(int i=n+1;i<=m;i++)
          if(a[i].z==2)
              cout<<ans[i]<<"\n";
  
      return 0;
  }

学习完毕

{{ select(1) }}

#edu2004. 基于时间的分治算法（cdq分治）

例 P3810三维偏序

例 P4169 [Violet] 天使玩偶/SJY摆棋子

学习完毕

状态

开发

支持

#edu2004. 基于时间的分治算法（cdq分治）

基于时间的分治算法（cdq分治）

例 P3810三维偏序

例 P4169 [Violet] 天使玩偶/SJY摆棋子

学习完毕

状态

开发

支持

还没有账户？

登录