P2086 [NOI2012] 魔幻棋盘 题解

FFTotoro · 2025-01-02 17:19:45 · 题解

考虑一种很暴力的做法。下文中令 S=NM，V=2^{62}-1（值域）。

为方便叙述，不妨设 N\le M。

考虑 N=1 时怎么做：一种情况是直接维护原来的操作（区间加 & 区间查询 \gcd）——但是这样似乎很难维护，那么是否能把区间加转换为单点加呢？

注意到 \gcd 具有良好的性质，即 \gcd(a,b)=\gcd(a,b-a)。所以对于一个序列 a 进行区间查询 [l,r] 时，有：

于是只需要维护 a 的差分序列：区间加变成了单点加，区间查询时，求 a_l 的值就是查询前缀和，求 \gcd\limits_{i=l+1}^r a_i-a_{i-1} 的值就是查询区间 \gcd。

由于 N\le M 且 NM=S，所以 N\le\sqrt{S}：这启发我们对于每一行开一棵线段树，操作时直接对于每棵线段树修改，查询时对于每棵线段树求出答案后合并即可。

设有 T 次询问，时间复杂度为 O(NM+TN\log M\log V)，即 O(S+T\sqrt{S}\log S\log V)，其中 \log V 是求 \gcd 的时间复杂度（代码实现中使用的是 std::gcd，需要使用 C++17 及以上的标准编译）。

上面的做法看起来在 S\le 5\times 10^5 的数据范围下过不去，但是我们可以使用非递归线段树（又称 zkw 线段树），这样就大大了减小常数；实测可以在 3.5\mathrm{s} 内通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class segtree{
  private:
    int k,m;
    vector<ll> s,g;
    inline void pushup(int u){
      s[u]=s[u<<1]+s[u<<1|1];
      g[u]=gcd(g[u<<1],g[u<<1|1]);
    }
  public:
    void init(vector<ll> a){
      k=__lg(a.size())+(__builtin_popcount(a.size())>1);
      s.resize((m=1<<k)<<1),g=s;
      for(int i=0;i<a.size();i++)
        s[i+m]=g[i+m]=a[i];
      for(int i=m-1;i;i--)
        pushup(i);
    }
    inline void update(int p,ll d){
      s[p+=m]+=d,g[p]+=d;
      for(int i=1;i<=k;i++)
        pushup(p>>i);
    } // 单点修改
    inline ll query_sum(int l,int r){
      ll c=0; l+=m,r+=m;
      while(l<r){
        if(l&1)c+=s[l++];
        if(r&1)c+=s[--r];
        l>>=1,r>>=1;
      }
      return c;
    } // 区间求和
    inline ll query_gcd(int l,int r){
      ll w=0; l+=m,r+=m;
      while(l<r){
        if(l&1)w=gcd(w,g[l++]);
        if(r&1)w=gcd(w,g[--r]);
        l>>=1,r>>=1;
      } // 区间求 gcd
      return w;
    }
}; // 非递归线段树
int main(){
  ios::sync_with_stdio(false);
  int n,m,x,y,q; cin>>n>>m>>x>>y>>q,x--,y--;
  bool f=n>m; if(f)swap(n,m),swap(x,y); // 处理 n>m 的情况
  vector a(n,vector<ll>(m));
  if(f){
    for(int i=0;i<m;i++)
      for(int j=0;j<n;j++)
        cin>>a[j][i];
  }
  else for(auto &i:a)for(auto &j:i)cin>>j;
  vector<segtree> t(n);
  for(int i=0;i<n;i++){
    vector<ll> d(m);
    adjacent_difference(a[i].begin(),a[i].end(),d.begin());
    t[i].init(d);
  } // 预处理差分序列
  while(q--){
    int op; cin>>op;
    if(op){
      int xa,ya,xb,yb; ll d; cin>>xa>>ya>>xb>>yb>>d,xa--,ya--,xb--,yb--;
      if(f)swap(xa,ya),swap(xb,yb);
      for(int i=xa;i<=xb;i++)
        if(t[i].update(ya,d);yb+1<m)t[i].update(yb+1,-d);
    } // 修改
    else{
      int xa,ya,xb,yb; ll c=0; cin>>xa>>ya>>xb>>yb;
      if(f)swap(xa,ya),swap(xb,yb);
      for(int i=x-xa;i<=x+xb;i++)
        c=gcd(c,gcd(t[i].query_gcd(y-ya+1,y+yb+1),t[i].query_sum(0,y-ya+1)));
      cout<<c<<'\n';
    } // 查询
  }
  return 0;
}