P4735 最大异或和 题解

· · 题解

传送门：P4735 最大异或和

本题解致力于阐述三种不同方法。它们之间联系紧密，算法优秀程度也层层递进。

一、可持久化 01-Trie（朴素版）

先推一波式子：

\quad a_p⊕a_{p+1}⊕a_{p+2}⊕...⊕a_{n-1}⊕a_n⊕x =(a_1⊕a_2⊕...⊕a_n)⊕(a_1⊕a_2⊕...⊕a_{p-1})⊕x =s_n⊕s_{p-1}⊕x\quad (s_m=a_1⊕a_2⊕...⊕a_m$，特别的，$s_0=0) =s_{p-1}⊕(s_n⊕x)\quad (l-1\le p-1\le r-1)

还记得 01-Trie 吗？智商 180 的它可以在线 O(log_2^n) 执行两种操作：① 在序列 a 中插入自然数 x。② 给定一个 x，询问 \max\{a_i⊕x\}。

本题可以视为在操作 ② 里加一限制：l-1\le i\le r-1，即询问 \max\{s_{l-1\sim r-1} ⊕ (s_n⊕x)\}。

如果 Trie_{r-1}-Trie_{l-2}=Trie_{l-1\sim r-1} （满足相消性），我们可以维护可持久化 01-Trie，在线解决问题。

普通 01-Trie 不满足相消性，不妨令 sum_i 表示有多少 x 插入时流经节点 i。易得 Trie_{l-1\sim r-1}sum_i=Trie_{r-1}sum_i-Trie_{l-2}sum_i。此式 =0 时无法走节点 i，>0 时可以走节点 i。

概述可持久化 01-Trie：

回顾可持久化数据结构的设计宗旨：在不破坏历史版本的情况下，新建尽量少的节点得到当前版本树。具体些：只沿用那些子树（包括本身）信息都未变化的节点。即使本身信息未变，但子树信息变化了，也要新开一个新节点。

插入 x 后，所有沿途的 sum_i 都将 +1，其余的 sum_i 保持不变。因此，我们只需新建沿途的节点，而沿用未经过的节点。

算法流程：设 Trie_i=Trie_{i-1}+x，我们从 p=root_i 开始，不断重复如下操作，直至插入 x 完毕：把 p 在 Trie_{i-1} 里对应节点的信息复制到 p 上（如没有对应节点，可视其为节点 0。l_0,r_0 均为空节点，sum_0=0）。然后把 sum_p+1，并令 p\rightarrow son_{p,0/1}（新建一个节点）。

利用相消性查询即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=600005;
int n,m;
int s[N];
int ch[N*25][2],sum[N*25];
int root[N],idx;
void insert(int x,int y,int i){
    sum[x]=sum[y]+1;
    for(int k=23;k>=0;k--){
        int c=(s[i]>>k)&1;
        ch[x][!c]=ch[y][!c];
        ch[x][c]=++idx;
        x=ch[x][c],y=ch[y][c];
        sum[x]=sum[y]+1;
    }
}
int query(int x,int y,int v){
    int ans=0;
    for(int k=23;k>=0;k--){
        int c=(v>>k)&1;
        if(sum[ch[x][!c]]-sum[ch[y][!c]]) ans+=(1<<k),x=ch[x][!c],y=ch[y][!c];
        else x=ch[x][c],y=ch[y][c];
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]),s[i]^=s[i-1];
    root[0]=++idx,insert(root[0],0,0);
    for(int i=1;i<=n;i++) root[i]=++idx,insert(root[i],root[i-1],i);
    while(m--){
        char ch[2];scanf("%s",ch);
        if(ch[0]=='A'){
            int x;scanf("%d",&x);
            root[++n]=++idx;
            s[n]=s[n-1]^x;
            insert(root[n],root[n-1],n);
        }else{
            int l,r,x;scanf("%d%d%d",&l,&r,&x);
            l--,r--;
            printf("%d\n",query(root[r],(l?root[l-1]:0),s[n]^x));
        }
    }
    return 0;
}

二、可持久化 01-Trie（升级版）

可持久化数据结构 S，求 S_{l\sim r} 一般采用相消法（法一）。“条条大路通罗马”，不妨换个思路。

我们能否只利用 Trie_r，不利用 Trie_{l-1} 就求出 Trie_{l\sim r}？这看似不太现实，但一个现实又摆在眼前，Trie_r 用到了之前版本的节点！

我们用 ver_i 表示节点 i 最晚在插入 x_{ver_i} 时被流经，查询时把判定条件 sum[ch[x][!c]]-sum[ch[y][!c]]>=0 改成 ver[ch[x][!c]]>=L 即可避免使用 Trie_{l-1}。

直白些，就是判断是否存在 l\le k\le r，满足插入 x_k 时流经节点 i。Trie_r 里包括且只包括所有插入 x_{k\le r} 时流经的节点，据此条件简化为 l\le k。对于每个节点 i，我们只需记录最大的 k（ver_i）即可。

那怎么求 ver_i 呢？在插入过程中加上一句 ver[x]=i 即可！

代码：

#include<bits/stdc++.h>
using namespace std;
#define FIO 
struct IO{
#ifdef FIO
const static int BUFSIZE=1<<20;char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;inline char getchar(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}inline void putchar(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}inline void flush(){fwrite(obuf,1,pp-obuf,stdout);}IO(){fwrite("Warning: Macro 'FIO' has been defined, keyboard input will be ignored.\n",1,71,stderr);p1=buf,p2=buf,pp=obuf;}~IO(){fwrite(obuf,1,pp-obuf,stdout);}
#else
int(*getchar)()=&::getchar;int(*putchar)(int)=&::putchar;inline void flush(){};
#endif
string sep=" ";int k=2;template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();s*=f;return ch!=EOF;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF&&ch!='.')f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();if(ch==EOF)return false;if(ch=='.'){Tp eps=0.1;ch=getchar();while(isdigit(ch))s=s+(ch^48)*eps,ch=getchar(),eps/=10;}s*=f;return ch!=EOF;}inline int read(char&c){char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();if(ch!=EOF)c=ch;return ch!=EOF;}inline int read(char*c){char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)*(c++)=ch,ch=getchar();return ch!=EOF;}inline int read(string&s){s.clear();char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)s+=ch,ch=getchar();return ch!=EOF;}inline int getline(char*c,const char&ed='\n'){char ch=getchar();while(ch!=ed&&ch!=EOF)*(c++)=ch,ch=getchar();return ch!=EOF;}inline int getline(string&s,const char&ed='\n'){s.clear();char ch=getchar();while(ch!=ed&&ch!=EOF)s+=ch,ch=getchar();return ch!=EOF;}template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}template<typename Tp,typename...Ts>int read(Tp&x,Ts&...val){return read(x)&&read(val...);}template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>IO&write(Tp x){if(x<0)putchar('-'),x=-x;static char sta[20];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)putchar(sta[--top]);return*this;}inline IO&write(const string&str){for(char ch:str)putchar(ch);return*this;}inline IO&write(const char*str){while(*str!='\0')putchar(*(str++));return*this;}inline IO&write(char*str){return write((const char*)str);}inline IO&write(const char&ch){return putchar(ch),*this;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline IO&write(Tp x){const static long long pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,100000000000000000,100000000000000000};const auto&n=pow10[k];if(x==0){putchar('0'),putchar('.');for(int i=1;i<=k;++i)putchar('0');return*this;}if(x<0)putchar('-'),x=-x;long long d=(long long)(x+1e-12),y=(long long)(x*n+0.5);write(d),putchar('.');static char sta[20];int top=0;for(;top<k;y/=10)sta[top++]=y%10^48;while(top)putchar(sta[--top]);return*this;}template<typename Tp,typename...Ts>inline IO&write(Tp x,Ts...val){write(x);write(sep);write(val...);return*this;}template<typename...Ts>inline IO&writeln(Ts...val){write(val...);putchar('\n');return*this;}inline IO&writeln(void){putchar('\n');return*this;}template<typename Tp>inline IO&writeWith(Tp x,const string&s){write(x),write(s);return*this;}inline IO&setsep(const string&s){return sep=s,*this;}inline IO&setprecision(const int&K){return k=K,*this;}}io;
const int N=600005;
int n,m;
int s[N];
int ch[N*25][2];
int root[N],idx;
int ver[N*25];
inline void insert(int x,int y,int i){
    ver[x]=i;
    for(int k=23;k>=0;k--){
        int c=(s[i]>>k)&1;
        ch[x][!c]=ch[y][!c];
        ch[x][c]=++idx;
        x=ch[x][c],y=ch[y][c];
        ver[x]=i;
    }
}
inline int query(int x,int L,int v){
    int ans=0;
    for(int k=23;k>=0;k--){
        int c=(v>>k)&1;
        if(ver[ch[x][!c]]>=L) x=ch[x][!c],ans+=(1<<k);
        else x=ch[x][c];
    }
    return ans;
}
int main(){
    io.read(n,m);
    for(int i=1;i<=n;i++) io.read(s[i]),s[i]^=s[i-1];
    ver[0]=-1;
    root[0]=++idx,insert(root[0],0,0);
    for(int i=1;i<=n;i++) root[i]=++idx,insert(root[i],root[i-1],i);
    while(m--){
        char ch;io.read(ch);
        if(ch=='A'){
            io.read(s[++n]);
            s[n]^=s[n-1];
            root[n]=++idx,insert(root[n],root[n-1],n);
        }else{
            int l,r,x;io.read(l,r,x);
            io.writeln(query(root[r-1],l-1,s[n]^x));
        }
    }
    return 0;
}

三、离线 + 01-Trie

法二中的函数 query 只与 Trie_r 有关。我们可以把所有询问离线下来，按 r 升序排列，边插入边处理。

代码：

#include<bits/stdc++.h>
using namespace std;
#define FIO 
struct IO{
#ifdef FIO
const static int BUFSIZE=1<<20;char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;inline char getchar(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}inline void putchar(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}inline void flush(){fwrite(obuf,1,pp-obuf,stdout);}IO(){fwrite("Warning: Macro 'FIO' has been defined, keyboard input will be ignored.\n",1,71,stderr);p1=buf,p2=buf,pp=obuf;}~IO(){fwrite(obuf,1,pp-obuf,stdout);}
#else
int(*getchar)()=&::getchar;int(*putchar)(int)=&::putchar;inline void flush(){};
#endif
string sep=" ";int k=2;template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();s*=f;return ch!=EOF;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF&&ch!='.')f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();if(ch==EOF)return false;if(ch=='.'){Tp eps=0.1;ch=getchar();while(isdigit(ch))s=s+(ch^48)*eps,ch=getchar(),eps/=10;}s*=f;return ch!=EOF;}inline int read(char&c){char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();if(ch!=EOF)c=ch;return ch!=EOF;}inline int read(char*c){char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)*(c++)=ch,ch=getchar();return ch!=EOF;}inline int read(string&s){s.clear();char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)s+=ch,ch=getchar();return ch!=EOF;}inline int getline(char*c,const char&ed='\n'){char ch=getchar();while(ch!=ed&&ch!=EOF)*(c++)=ch,ch=getchar();return ch!=EOF;}inline int getline(string&s,const char&ed='\n'){s.clear();char ch=getchar();while(ch!=ed&&ch!=EOF)s+=ch,ch=getchar();return ch!=EOF;}template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}template<typename Tp,typename...Ts>int read(Tp&x,Ts&...val){return read(x)&&read(val...);}template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>IO&write(Tp x){if(x<0)putchar('-'),x=-x;static char sta[20];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)putchar(sta[--top]);return*this;}inline IO&write(const string&str){for(char ch:str)putchar(ch);return*this;}inline IO&write(const char*str){while(*str!='\0')putchar(*(str++));return*this;}inline IO&write(char*str){return write((const char*)str);}inline IO&write(const char&ch){return putchar(ch),*this;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline IO&write(Tp x){const static long long pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,100000000000000000,100000000000000000};const auto&n=pow10[k];if(x==0){putchar('0'),putchar('.');for(int i=1;i<=k;++i)putchar('0');return*this;}if(x<0)putchar('-'),x=-x;long long d=(long long)(x+1e-12),y=(long long)(x*n+0.5);write(d),putchar('.');static char sta[20];int top=0;for(;top<k;y/=10)sta[top++]=y%10^48;while(top)putchar(sta[--top]);return*this;}template<typename Tp,typename...Ts>inline IO&write(Tp x,Ts...val){write(x);write(sep);write(val...);return*this;}template<typename...Ts>inline IO&writeln(Ts...val){write(val...);putchar('\n');return*this;}inline IO&writeln(void){putchar('\n');return*this;}template<typename Tp>inline IO&writeWith(Tp x,const string&s){write(x),write(s);return*this;}inline IO&setsep(const string&s){return sep=s,*this;}inline IO&setprecision(const int&K){return k=K,*this;}}io;
const int N=600005;
int n,m;
int s[N];
int ch[N*25][2];
int idx=1;
int ver[N*25];
int head[N],nxt[N],L[N],X[N],id[N],tot;
int qct,ans[N];
inline void add(int u,int L1,int X1,int id1){
    L[++tot]=L1,X[tot]=X1,id[tot]=id1;
    nxt[tot]=head[u];
    head[u]=tot;
}
inline void insert(int x,int i){
    ver[x]=i;
    for(int k=23;k>=0;k--){
        int c=(s[i]>>k)&1;
        if(!ch[x][c]) ch[x][c]=++idx;
        ver[x=ch[x][c]]=i;
    }
}
inline int query(int x,int L,int v){
    int ans=0;
    for(int k=23;k>=0;k--){
        int c=(v>>k)&1;
        if(ver[ch[x][!c]]>=L) x=ch[x][!c],ans+=(1<<k);
        else x=ch[x][c];
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head));
    io.read(n,m);
    for(int i=1;i<=n;i++) io.read(s[i]),s[i]^=s[i-1];
    ver[0]=-1;
    while(m--){
        char ch[2];io.read(ch);
        if(ch[0]=='A'){
            io.read(s[++n]);
            s[n]^=s[n-1];
        }else{
            int l,r,x;io.read(l,r,x);
            add(r-1,l,s[n]^x,++qct);
        }
    }
    for(int i=0;i<=n;i++){
        insert(1,i);
        for(int k=head[i];~k;k=nxt[k]) ans[id[k]]=query(1,L[k]-1,X[k]);
    }
    for(int i=1;i<=qct;i++) io.writeln(ans[i]);
    return 0;
}

本代码抢到了最优解第 2 名，强烈 zc！