题解：P8526 [Ynoi2078] 《How to represent part-whole hierarchies in a neural network》阅读报告（更新中...）

wzr0507 · 2026-07-24 07:54:46 · 题解

一句话题意：静态查询子区间颜色数量异或和。

一般颜色数量显然使用扫描线维护第一次最后一次出现。在本题似乎没有更好的利用方式了，所以直接扫描 r 转换为黑盒。

那么问题被化为了区间加 1 区间历史异或和。这是困难的，线段树显然死了（应该不会真有人做到 polylog 吧），考虑分块。

一个简单的思路是使用序列分块进行扫描线。考虑序列分块要维护的是啥。

不论整散块，区间加 1 操作都是平凡的。直接做。考虑更新历史版本怎么做。

整块每次需要 O(1) 求出 \bigoplus_{i=l}^r(a_i+x)。这显然是极其困难的。考虑对整块提前预处理出。

但预处理显然不可能对 n 个数全部预处理，否则散块重构复杂度将完全无法接受。由于只有加 1 考虑使用定期重构手法，在 x 达到 B 重新预处理。

这个东西显然已经可以在 O(B\log{B}) 复杂度内求出了，大概做法是对每个二进制位拆位前缀和数点即可。于是先考虑散块。

发现散块唯一难点在于更新历史版本。然而观察后发现，更新单点历史版本的操作与 \bigoplus_{i=l}^r(a_i+x) 的子问题是及其类似的，只是此时 a 的值域缩减为了 B，x 的值域增长为 n。对于高于 B 的位只会产生一次进位，可以前缀和线性处理。所以 x 值域即可缩减为 O(B)。于是该问题被划归为 \bigoplus_{i=l}^r(a_i+x)，于是本问题得以在 O(n\sqrt{n}\log{n}) 时间内求解。

考虑优化求 \bigoplus_{i=l}^r(a_i+x) 的子问题。对 \ge{B} 的二进制位最多产生一次进位，直接暴力考虑，于是 a_i\le{B}。此时预处理出 f_i,_j 表示 a\mod{2^i}=j 的数量。请注意此时状态数为 \sum{2^i}=O(B)。预处理的手法可以按 i 从大到小合并。注意到，直接拆位数点的 O(B\log{B}) 做法，在考虑第 i 位答案时其实只关心 x\mod{2^{i+1}} 与 a\mod{2^{i+1}}。于是按 i 从小到大，每层直接线性做前缀和算出来答案即可。

子问题的具体实现可以参考代码。

void solve(int len)
{
    memset(dp[V],0,sizeof dp[V]);
    for(int i=1;i<=len;i++)
    dp[V][A[i]]^=1;
    for(int i=V-1;i>=0;i--)
    {
        for(int j=0;j<(1<<i);j++)
        dp[i][j]=dp[i+1][j]^dp[i+1][j+(1<<i)];
    }//dp[i][j]表示%2^i=j数量 
    for(int i=V;i>=0;i--)
    {
        for(int j=(1<<i)-1;j>=1;j--)
        dp[i][j-1]^=dp[i][j];
    }//dp[i][j]表示%2^i>=j数量 
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<(1<<i+1);j++)
        f[i+1][j]=dp[i+1][2*(1<<i)-j];
        for(int j=(1<<i)+1;j<(1<<i+1);j++)
        f[i+1][j]^=dp[i+1][3*(1<<i)-j];
        for(int j=0;j<(1<<i);j++)
        f[i+1][j]^=dp[i+1][(1<<i)-j];
        for(int j=(1<<i);j<(1<<i+1);j++)
        f[i+1][j]^=dp[i+1][0];
        //f_x表示%2^(i+1)=x的x第i位是否为1 
        for(int j=0;j<(1<<i);j++)
        f[i+1][j]=(f[i+1][j]<<i)|f[i][j],f[i+1][j+(1<<i)]=(f[i+1][j+(1<<i)]<<i)|f[i][j];
        //f_x表示%2^(i+1)=x的前i位 
    }
    for(int i=0;i<(1<<V);i++)
    as[i]=f[V][i];
    return;
}

给出完整代码实现。

#include<bits/stdc++.h>
using namespace std;
const int N=400010,V=8,B=(1<<V);
struct node
{
    int id,l,r;
}qu[400010];
bool cmp(node x,node y)
{
    return x.r<y.r;
}
int c[400010],aa[400010];
int A[B+5];
bool dp[(1<<V+1)+5];
uint8_t f[(1<<V+1)+5],g[(1<<V)+5];
template<int I>void AAAAA()
{
    for(int j=(1<<I);j<(2<<I);j++)dp[j]=dp[j+(1<<I)]^dp[j+(2<<I)];
}
template<int I>void BBBBB()
{
    for(int j=(2<<I)-1;j>=(1<<I)+1;j--)dp[j-1]^=dp[j];
}
template<int I>void CCCCC()
{
    for(int j=0;j<(1<<I);j++)
    g[j]=dp[j+(2<<I)]^dp[j+(3<<I)];
    g[(1<<I)]=g[0]^dp[(2<<I)];
    for(int j=0;j<(1<<I);j++)
    f[j]|=g[(1<<I)-j]<<I;
    for(int j=0;j<(1<<I);j++)
    f[j+(1<<I)]=f[j]^(dp[(2<<I)]<<I);
}
void solve(int len,int op)
{
    f[0]=0;
    if(op)
    {
        memset(dp+(1<<V),0,sizeof(bool)*(1<<V));
        for(int i=1;i<=len;i++)
        dp[A[i]+(1<<V)]^=1;
    }
    AAAAA<7>();
    AAAAA<6>();
    AAAAA<5>();
    AAAAA<4>();
    AAAAA<3>();
    AAAAA<2>();
    AAAAA<1>();
    AAAAA<0>();
    BBBBB<8>();
    BBBBB<7>();
    BBBBB<6>();
    BBBBB<5>();
    BBBBB<4>();
    BBBBB<3>();
    BBBBB<2>();
    BBBBB<1>();
    BBBBB<0>();
    CCCCC<0>();
    CCCCC<1>();
    CCCCC<2>();
    CCCCC<3>();
    CCCCC<4>();
    CCCCC<5>();
    CCCCC<6>();
    CCCCC<7>();
}
int n,m,a[400010],b[400010],ini[N/B+5][(1<<V)+5],sum[N/B+5],add[N/B+5];
bool tag[N/B+5][(1<<V)+5];
void rebuildb(int id)//借助tag更新出块中所有的b，并加入到块历史异或和sum中,并清空tag 
{
    int len=0;
    memcpy(dp+(1<<V),tag[id],sizeof tag[id]);
    int l=max(id*B,1),r=min((id+1)*B-1,n);
    for(int i=1;i<(1<<V);i++)
    tag[id][i]^=tag[id][i-1];//tag_i表示<=i的数量 
    solve(len,0);
    len=tag[id][(1<<V)-1];
    if(len==0)
    {
        for(int i=l;i<=r;i++)
        {
            int op=a[i]&((1<<V)-1),x1=tag[id][(1<<V)-1-op];
            b[i]^=f[op];
            if(x1&1)
            b[i]^=(a[i]^op)^((a[i]^op)+(1<<V));
        }
    }
    else
    {
        for(int i=l;i<=r;i++)
        {
            int op=a[i]&((1<<V)-1),x1=tag[id][(1<<V)-1-op];
            b[i]^=f[op];
            if(x1&1)
            b[i]^=(a[i]^op);
            else
            b[i]^=(a[i]^op)+(1<<V);
        }
    }
    memset(tag[id],0,sizeof tag[id]);
    return;
}
void init(int id)//只需求出ini即可 
{
    memset(ini[id],0,sizeof ini[id]);
    int l=max(id*B,1),r=min((id+1)*B-1,n);
    for(int i=l;i<=r;i++)
    {
        int op=a[i]&((1<<V)-1);
        ini[id][0]^=a[i]-op;
        ini[id][(1<<V)-op]^=(a[i]-op)^(a[i]-op+(1<<V));
        A[i-l+1]=op;
    }
    for(int i=1;i<(1<<V);i++)
    ini[id][i]^=ini[id][i-1];
    solve(r-l+1,1);
    for(int i=0;i<(1<<V);i++)
    ini[id][i]^=f[i];
    return;
}
void rebuild(int id,int l,int r,int op)
{
    if(add[id]==0&&tag[id][add[id]]==0&&l>r)
    return;
    int L=max(id*B,1),R=min((id+1)*B-1,n);
    if(add[id]!=0||tag[id][add[id]]!=0)
    rebuildb(id);
    for(int i=L;i<=R;i++)
    a[i]+=add[id];
    for(int i=l;i<=r;i++)
    a[i]++;
    add[id]=0;
    if(op==1)
    init(id);
    else
    {
        ini[id][0]=0;
        for(int i=L;i<=r;i++)
        ini[id][0]^=a[i];
    }
    return;
}
void update(int l,int r)
{
    if(l/B==r/B)
    {
        int id=l/B;
        rebuild(id,l,r,r%B==B-1);
        return;
    }
    int lid=l/B,rid=r/B;
    rebuild(lid,l,min((lid+1)*B-1,n),1);
    rebuild(rid,max(rid*B,1),r,r%B==B-1);
    for(int i=lid+1;i<rid;i++)
    add[i]++;
    return;
}
inline void uphis(int id)
{
    tag[id][add[id]]^=1;
    sum[id]^=ini[id][add[id]];
    if(add[id]==(1<<V)-1)
    rebuild(id,1,0,1);
    return;
}
int query(int l,int r)
{
    if(l/B==r/B)
    {
        int ans=0;
        rebuild(l/B,1,0,r%B==B-1);
        for(int i=l;i<=r;i++)
        ans^=b[i];
        return ans;
    }
    int ans=0,lid=l/B,rid=r/B;
    rebuild(lid,1,0,1);
    rebuild(rid,1,0,r%B==B-1);
    for(int i=l;i<=min((lid+1)*B-1,n);i++)
    ans^=b[i];
    for(int i=max(rid*B,1);i<=r;i++)
    ans^=b[i];
    for(int i=lid+1;i<rid;i++)
    ans^=sum[i];
    return ans;
}
int lastans[N+5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i],aa[i]=a[i];
    int l,r;
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        qu[i]={i,l,r};
    }
    sort(qu+1,qu+m+1,cmp);
    memset(a,0,sizeof a);
    for(int i=0,j=0;i<=n;i++)
    {
        if(i)
        {
            update(c[aa[i]]+1,i);//区间加 
            c[aa[i]]=i;
        }
        for(int id=0;id<=i/B;id++)
        uphis(id);
        while(j<m&&qu[j+1].r<=i)
        {
            j++;
            lastans[qu[j].id]^=query(qu[j].l,i);
        }
    }
    for(int i=1;i<=m;i++)
    cout<<lastans[i]<<'\n';
    return 0;
}