【纪中集训2019.3.14】小凯的疑惑

题目

描述:

\(n\)个点的完全图，每个点有一个\(C\)为二进制权值\(X_{i}\)，$W(u,v) = X_{u} xor X_{v} $

求这个图的最小生成树，支持\(Q\)次修改，每次修改将所有点权值\(+V\)，询问具有后效性；

题目：

\(1 \le n \le 20000 , C \le 14 , 1 \le Q \le 20000\)

题解：

• 算法一：

• 首先答案和\(n\)无关权值只有\(2^C\)中，询问最多也是\(2^C\)种 ，可以预处理所有询问 ；

• 考虑经典的异或生成树的做法 ；

• 按照二进制的最高位分治，内部的边比跨越两边的边都要优，在\(Trie\)里查找两两连边的最小值 ；

• 复杂度：\(O(2^C \times C^22^C)\) ；

• 算法二：

• 对于一个询问\(Q_{i}\)，将它分成后\(B\)位和前\(C - B\) 位；

• 在分治树上，记从下到上为\(0 \to C-1\) 层 ;

• $Q_{i} \(后\)C-B\(位的贡献相当于将第\)B$层的分治子树向右整体平移；

• \(Q_{i}\)前\(B\)位的贡献相当于只在?\(B\)层之前的叶子平移，对B层以上的结构没有影响；

• 预处理一个询问的前\(B\)位 确定时\(B\) 层的每个节点分治下去的答案和两两之间合并的答案；

• 对于后$C - B $位直接分治；

• 复杂度：\(O( 2^{C+B}B^2 + 2^{2C-B}B)\)

• 大致\(B\)取\(\frac{n}{2}\)比较好

• 算法三：

• 对前\(B\)层的求解可以再进行优化：

• 预处理前\(A(A \lt B)\)每个叶子节点的答案和两两之间合并的答案；

• 考虑到\(A\)比较小，可以直接枚举\(2^{2^{A}}\)颗子树暴力求解，当分治到第\(A\)层时直接调用答案；

• 复杂度：\(O((2^{2^{A}+1})2^AA \ + \ 2^{2^{A}}2^AA^{2} + 2^{C}2^{B-A}(B-A)^2 \ + \ 2^{2C-A}(B-A) + 2^{2C-B}(C-B)^2)\)

• （省略一些近似于常数的东西可能大家的写法有点出入）

• 这样子\(C==14\)的情况\(A\)取\(3\)，\(B\)取\(7\)即可；、

  #include<bits/stdc++.h>
  #define fir first
  #define sec second 
  #define mk make_pair
  #define inf 0x3f3f3f3f
  using namespace std;
  typedef pair<int,int>pii;
  int n,q,A,B,C,sum[1<<15],a[1<<15],mask[1<<15];
  int v[1<<3],g[1<<8],G[1<<8][1<<8],f[1<<7][1<<7],F[1<<7][1<<7][1<<7],ans[1<<15];
  inline int min(int x,int y){return x<y?x:y;}
  struct Trie{
    int sz,ch[1<<15][2],val[1<<15];
    void init(){
        for(int i=1;i<=sz;++i)ch[i][0]=ch[i][1]=val[i]=0;
        sz=1;
    }
    void ins(int x,int l,int r,int y){
        int now=1;
        for(int i=r-1;i>=l;--i){
            int t=x>>i&1;
            if(ch[now][t])now=ch[now][t];
            else ch[now][t]=++sz,now=sz;
        }
        val[now]=y;
    }
    pii que(int x,int l,int r){
        int res=0,now=1;
        for(int i=r-1;i>=l;--i){
            int t=x>>i&1;
            if(ch[now][t])now=ch[now][t];
            else now=ch[now][t^1],res^=1<<i;
        }
        return mk(res,val[now]);
    }
  }T;
  bool ask(int x,int y){
    if(!x)return sum[y-1];
    return sum[y-1]-sum[x-1];
  }
  void init(){
    for(int i=0;i<1<<C;++i)a[i+(1<<C)]=a[i];
    for(int i=0;i<1<<C+1;++i)sum[i]=sum[i-1]+a[i];
    for(int i=0;i<1<<C;++i)
    for(int j=0;j<1<<A;++j)mask[i]|=a[i+j]<<j;
    for(int i=0;i<1<<C;++i)mask[i+(1<<C)]=mask[i];
  }
  int solveg(int l,int r){
    if(l+1==r)return 0;
    int mid=(l+r)>>1,fg;
    fg=0;
    for(int i=l;i<mid;++i)if(v[i]){fg=1;break;}
    if(!fg)return solveg(mid,r);
    fg=0;
    for(int i=mid;i<r;++i)if(v[i]){fg=1;break;}
    if(!fg)return solveg(l,mid);
    T.init();
    for(int i=l;i<mid;++i)if(v[i])T.ins(i,0,A,i);
    int re=inf;
    for(int i=mid;i<r;++i)if(v[i])re=min(re,T.que(i,0,A).fir);
    return re + solveg(l,mid) + solveg(mid,r);
  }
  int solvef(const int s,int l,int r){
    if(l+1==r)return g[mask[s+(l<<A)]];
    int mid=(l+r)>>1,fg;
    fg=0;
    for(int i=l;i<mid;++i)if(ask(s+(i<<A),s+(i+1<<A))){fg=1;break;}
    if(!fg)return solvef(s,mid,r);
    fg=0;
    for(int i=mid;i<r;++i)if(ask(s+(i<<A),s+(i+1<<A))){fg=1;break;}
    if(!fg)return solvef(s,l,mid);
    T.init();
    for(int i=l;i<mid;++i)if(ask(s+(i<<A),s+(i+1<<A))){
        T.ins(i<<A,A,B,s+(i<<A));
    }
    int re=inf;
    for(int i=mid;i<r;++i)if(ask(s+(i<<A),s+(i+1<<A))){
        pii r = T.que(i<<A,A,B);
        re = min(re, r.fir + G[mask[s+(i<<A)]][mask[r.sec]]);
    }
    return re + solvef(s,l,mid) + solvef(s,mid,r); 
  }
  int solveans(const int s,int l,int r){
    int S1=(1<<B)-1,S2=(1<<C-B)-1;
    if(l+1==r)return f[s&S1][l+(s>>B)&S2];
    int mid=(l+r)>>1,fg;
    fg=0;
    for(int i=l;i<mid;++i)if(ask(s+(i<<B),s+(i+1<<B))){fg=1;break;}
    if(!fg)return solveans(s,mid,r);
    fg=0;
    for(int i=mid;i<r;++i)if(ask(s+(i<<B),s+(i+1<<B))){fg=1;break;}
    if(!fg)return solveans(s,l,mid);
    T.init();
    for(int i=l;i<mid;++i)if(ask(s+(i<<B),s+(i+1<<B))){
        T.ins(i<<B,B,C,i+(s>>B)&S2);
    }
    int re=inf;
    for(int i=mid;i<r;++i)if(ask(s+(i<<B),s+(i+1<<B))){
        pii r = T.que(i<<B,B,C);
        re = min(re, r.fir + F[s&S1][i+(s>>B)&S2][r.sec]);
    }
    return re + solveans(s,l,mid) + solveans(s,mid,r);
  }
  void calcg(){
    for(int i=0;i<1<<(1<<A);++i){
        for(int j=0;j<1<<A;++j)v[j]=i>>j&1;
        g[i]=solveg(0,1<<A);
    }
  }
  void calcG(){
    for(int i=0;i<1<<(1<<A);++i){
        T.init();
        for(int j=0;j<1<<A;++j)if(i>>j&1){T.ins(j,0,A,j);}
        for(int j=0;j<1<<A;++j){G[i][1<<j]=T.que(j,0,A).fir;}
        for(int j=0;j<1<<(1<<A);++j){if(j^(j&-j))G[i][j]=min(G[i][j^(j&-j)],G[i][j&-j]);}
    }
  }
  void calcf(){
    for(int i=0;i<1<<B;++i)
    for(int j=0;j<1<<C-B;++j){
        f[i][j]=solvef(i,j<<B-A,j+1<<B-A);
    }
  }
  void calcF(){
    for(int i=0;i<1<<B;++i)
    for(int j=0;j<1<<C-B;++j){
        T.init();
        int fg=0;
        for(int k=j<<B-A;k<j+1<<B-A;++k)if(ask(i+(k<<A),i+(k+1<<A))){
            T.ins(k<<A,A,B,i+(k<<A));fg=1;
        }
        if(!fg)continue;
        for(int k=0;k<1<<C-B;++k){
            fg=0;
            for(int l=k<<B-A;l<k+1<<B-A;++l)if(ask(i+(l<<A),i+(l+1<<A))){fg=1;break;}
            if(!fg){F[i][j][k]=0;continue;}
            F[i][j][k]=inf;
            for(int l=k<<B-A;l<k+1<<B-A;++l)if(ask(i+(l<<A),i+(l+1<<A))){
                pii r=T.que(l<<A,A,B);
                F[i][j][k]=min(F[i][j][k], r.fir+G[mask[i+(l<<A)]][mask[r.sec]]);
            }
        }
    }
  }
  void calcans(){
    for(int i=0;i<1<<C;++i)
    ans[i]=solveans(i,0,1<<C-B);
  }
  int main(){
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    scanf("%d%d",&n,&C);
    B=C>>1;A=B>>1;
    for(int i=1,x;i<=n;++i)scanf("%d",&x),a[x]=1;
    init();
    calcg();calcG();
    calcf();calcF();
    calcans();
    scanf("%d",&q);
    int S=(1<<C)-1;
    for(int i=1,x,y=0;i<=q;++i){
        scanf("%d",&x);
        y=(y+S+1-x)&S;
        printf("%d\n",ans[y]);  
    }
    return 0;
  }

【纪中集训2019.3.14】小凯的疑惑

原文：https://www.cnblogs.com/Paul-Guderian/p/10533410.html