P8257 题解

KSCD_ · 2025-09-18 21:44:59 · 题解

Update（26.01.14）：复杂度分析有误，已修改，感谢 @流泪的小酒窝 指出。

核桃周赛搬的，已严肃学习 hhoppitree 题解做法，记录一下。

题意

给定序列 a，q 次询问 [L,R] 内所有子区间权值异或和，区间权值定义为该区间内数字种类数。n,q\le 4\times 10^5，时间限制 10 秒。

题解

询问所有子区间考虑离线，按照右端点排序后扫描，并维护每个点到当前点的种类数 c_i。扫到询问右端点 R 时，[L,R] 的区间历史异或和即为答案。然而历史异或和还是太难了，考虑避免历史和。注意到若 t 时刻 c_i 未修改，则 t-1,t 两时刻的 c_i 相等，异或后会抵消掉。因此从后往前每两个时刻一起算，则 t-1,t 会贡献当且仅当 c_i 在 t 时刻被修改，贡献值为 c_{i,t-1}\oplus(c_{i,t-1}+1)。

将该贡献放到 t 时刻上，则历史和变成了奇偶性相同的若干时刻异或和。因此设 b_{i,0/1} 表示目前 i 处所有偶数 / 奇数时刻的总贡献，t 时刻修改即区间内 b_{i,t\bmod 2} 异或上 c_i\oplus(c_i+1)，之后 c_i 加一；查询即求区间 b_{i,R\bmod 2} 的异或和，这样就没有历史和了。

注意到 c_i\oplus(c_i+1) 的值只与 c_i 末尾 1 的个数 k 有关，该值为 2^{k+1}-1，因此大部分贡献值都很小。考虑根号分治，以 2^B 为界划分，则当且仅当 c_i 后 B 位均为 1 时贡献值会超过 2^B-1，而这每加 2^B 才会发生一次，每个位置只会发生 \frac n{2^B} 次，在 B 足够大时即可暴力修改。

因此现在只需快速维护 b 数组后 B 位的值。考虑对原序列每 S 个元素分一块，修改时对整块打标记并整体改动，散块下传标记后暴力修改，查询也是类似的，问题在于如何支持整体改。由于只考虑后 B 位，可对每个块预处理出 w_{i,v}，表示 i 块在 tag\bmod 2^B=v 时再操作一次对后 B 位的贡献。对该贡献拆位，则当且仅当 (c_i+v) 的后 j 位均为 1 时会产生 2^j 的贡献，此时 (c_i+v)\bmod 2^j=2^j-1，即 c_i 与 v 后 j 位互为补集。

考虑从低位到高位对所有 c_i 后 B 位建立 Trie 树，求 w_{i,v} 时在 Trie 树上找到 2^B-1-(v\bmod 2^B) 这条路径，则其第 j 层节点子树内均满足后 j 位与 v 互为补集，这些 (c_i+v) 会产生 2^j 贡献，因此当且仅当该子树大小为奇数时 2^j 位为 1。由于只关心子树大小，可预先建出树，c_i 直接贡献到叶子节点，之后遍历整棵 Trie 即可求出所有 w_{i,v}，时间复杂度单次 O(2^B)。整块修改时即可直接将值异或上 w_{i,tag_i}，再将 tag_i 加一。

另外需支持迅速找到整块内目前 c_i+tag\equiv {2^B-1}\pmod {2^B} 的所有位置，从而暴力更新高位信息。这需要在构建块时将所有 c_i 按照 c_i\bmod 2^B 排序，并记录每种值的区间，可以使用桶排。这样修改时只需要找到 2^B-1-(tag\bmod 2^B) 对应的区间，暴力修改其中所有位置即可。要注意这种修改不能影响到后 B 位，后 B 位的贡献是单独计算的。这样整个重构操作就做完了，单次复杂度 O(2^B+S)，常数比较大。

还需要解决标记下传问题，c_i 的更新是简单的，然而还需要更新所有 b 的值。考虑同样拆位算贡献，对所有 v\lt 2^B 记录下该块在 tag=v 情况下操作次数的奇偶性。下传时将所有奇数次的 v 放到 Trie 上，再查询 2^B-1-(c_i\bmod 2^B) 即可，单次复杂度同样是 O(2^B+S)。

分析出来总复杂度为 O(\frac{n^2}{2^B}+(n+q)(S+2^B+\frac nS))，取 2^B\approx S=\sqrt n 可以得到理论最优复杂度 O((n+q)\sqrt n)。然而其中 2^B 常数极大，实践发现取 B=7,2^B=128 跑得最快。另外 S 与 B 是独立的，但实践下来发现同样取 S=128 还是比较优的，因此下面的代码取了该块长。

代码

#include<iostream>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=4e5+10;
const int B=128;
const int M=B+10;
const int K=N/B+10;
int n,m,a[N],res[N],last[N],lp[N],lg[M],tp[M],id[N],L[K],R[K],c[N];
int tag[K],b[2][N],s[2][K],w[K][M],fp[K][M],po[K][M],g[2][M<<1];
bool t[K][2][M],ct[M<<1]; // t 也是标记，记录每个块每种值操作次数的奇偶性 
vector <pii> ask[N];
void build(int u,int d,int x)
{
    if((1<<d)==B) {tp[x]=u; return;}
    lg[u]=d,build(u<<1,d+1,x),build(u<<1|1,d+1,x|(1<<d));
} // 建出 B 位的 Trie，并预处理每种值的位置 tp_x 
void built(int id)
{
    s[0][id]=s[1][id]=0;
    for(int i=0;i<=B;i++)
    {
        w[id][i]=fp[id][i]=0;
        for(int o=0;o<2;o++) t[id][o][i]=0;
    } // 清空原信息 
    for(int i=0;i<(B<<1);i++) ct[i]=0;
    for(int i=L[id];i<=R[id];i++)
    {
        s[0][id]^=b[0][i],s[1][id]^=b[1][i];
        ct[tp[c[i]&(B-1)]]^=1,fp[id][B-1-(c[i]&(B-1))]++;
    }
    for(int i=1;i<=B;i++) fp[id][i]+=fp[id][i-1];
    for(int i=L[id];i<=R[id];i++) po[id][--fp[id][B-1-(c[i]&(B-1))]]=i; //类似桶排用 po 按值排序记录所有位置，fp 记录每种值的左端点 
    for(int i=B-1;i;i--) ct[i]=(ct[i<<1]^ct[i<<1|1]);
    g[0][1]=ct[1];
    for(int i=2;i<(B<<1);i++)
    {
        g[0][i]=g[0][i>>1];
        if(i<B) g[0][i]|=(ct[i]<<lg[i]);
    }
    for(int i=0;i<B;i++) w[id][i]=g[0][tp[B-1-(i&(B-1))]]; // 用 Trie 计算贡献数组 w  
}
void push(int id)
{
    for(int o=0;o<2;o++)
    {
        for(int i=0;i<(B<<1);i++) ct[i]=0;
        for(int i=0;i<B;i++) ct[tp[i]]^=t[id][o][i];
        for(int i=B-1;i;i--) ct[i]=(ct[i<<1]^ct[i<<1|1]);
        g[o][1]=ct[1];
        for(int i=2;i<(B<<1);i++)
        {
            g[o][i]=g[o][i>>1];
            if(i<B) g[o][i]|=(ct[i]<<lg[i]);
        }
    }
    for(int i=L[id];i<=R[id];i++)
    {
        for(int o=0;o<2;o++) b[o][i]^=g[o][tp[B-1-(c[i]&(B-1))]];
        c[i]+=tag[id];
    } // 同样用 Trie 进行 c 值的更新 
    tag[id]=0;
}
void pt(int o,int id)
{
    int v=(tag[id]&(B-1)); tag[id]++;
    s[o][id]^=w[id][v],t[id][o][v]^=1;
    for(int i=fp[id][v];i<fp[id][v+1];i++)
    {
        int p=po[id][i],d=((c[p]+tag[id])^(c[p]+tag[id]-1)^(B-1));
        s[o][id]^=d,b[o][p]^=d;
    }  // 暴力操作对高位产生影响的位置 
} // 操作一个整块 
void update(int o,int l,int r)
{
    int pl=id[l],pr=id[r];
    if(pl==pr)
    {
        push(pl);
        for(int i=l;i<=r;i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
        built(pl);
    }
    else
    {
        push(pl),push(pr);
        for(int i=l;i<=R[pl];i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
        for(int i=L[pr];i<=r;i++) c[i]++,b[o][i]^=c[i]^(c[i]-1);
        for(int i=pl+1;i<pr;i++) pt(o,i);
        built(pl),built(pr);
    }
}
int query(int o,int l,int r)
{
    int tr=0,pl=id[l],pr=id[r];
    if(pl==pr)
    {
        push(pl),built(pl);
        for(int i=l;i<=r;i++) tr^=b[o][i];
    }
    else
    {
        push(pl),push(pr),built(pl),built(pr);
        for(int i=l;i<=R[pl];i++) tr^=b[o][i];
        for(int i=L[pr];i<=r;i++) tr^=b[o][i];
        for(int i=pl+1;i<pr;i++) tr^=s[o][i];
    }
    return tr;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m,build(1,0,0);
    for(int i=1;i<=n;i++) cin>>a[i],lp[i]=last[a[i]]+1,last[a[i]]=i,id[i]=(i-1)/B+1,R[id[i]]=i;
    for(int i=n;i;i--) L[id[i]]=i;
    for(int i=1,l,r;i<=m;i++) cin>>l>>r,ask[r].pb({l,i});
    for(int i=1;i<=n;i++)
    {
        update(i&1,lp[i],i);
        for(pii te:ask[i]) res[te.se]=query(i&1,te.fi,i);
    }
    for(int i=1;i<=m;i++) cout<<res[i]<<'\n';
    return 0;
}