非常猛的一道 lxl 题，从傍晚 6 点研究到深夜 1 点才通过。
首先前一部分扫描线是平凡的：从小到大枚举右端点 \(r\)，枚举到 \(r\) 的时候对于所有 \(l\in [lst_{a_r}+1,r]\) 令 \(b_l\) 加一，这样查询相当于问 \(r\) 时刻 \([l,r]\) 历史异或和。
历史异或和看起来有点奇怪，我们考虑一个 \(i\in [l,r]\) 以及一个时刻 \(j\)，假设 \(j\) 这个时刻令 \(b_i\) 加了一，那么我们发现如果查询的时刻 \(r\) 与 \(j\) 奇偶性相同，那么这次修改会对 \(r\) 时刻 \(b_i\) 的历史版本异或和产生 \(b_i\oplus(b_i+1)\) 的贡献，否则贡献为零。这样相当于这样一个问题：
\(n\) 次操作，第 \(i\) 次操作给定一个区间 \([l,r]\)，\(\forall j\in[l,r]\)，令 \(b_j\) 加一，并令 \(c_{i\bmod 2,j}\) 异或上 \(b_j\oplus (b_j-1)\)。
\(q\) 次询问，形如“第 \(r\) 次操作后 \(c_{r\bmod 2,l}\oplus c_{r\bmod 2,l+1}\cdots\oplus c_{r\bmod 2,r}\) 的值是多少。
直接实现可以获得 40 分。
考虑怎么用数据结构维护之。显然无法 polylog，考虑分块。我们每 \(B\) 个元素分一块。这里我思考的时候想到了一个错解是，看到加一和异或，容易想到那个全局 \(+1\)，查全局异或和的 trie，但是这样只能维护整块信息，碰到单点就寄了，因此我们必须放弃这个思路。
考虑 \(x\oplus (x+1)\) 是个啥。找到 \(x\) 最低的 \(0\) 所在的位 \(2^h\)，这样 \(x\oplus (x+1)=2^{h+1}-1\)，也就是说我们只关心 \(b_j\) 最低的为 \(0\) 的位，但是这样还是不足以很好地维护这个数据结构，因为你发现非常棘手的地方在于，对于一个二进制位 \(2^h\)，要判断 \(b_j\bmod 2^{h+1}\) 是否恰好等于 \(2^{h}-1\)（也就是恰好在 \(2^h\) 这一位进位），需要维护大小与 \(2^h\) 同阶的桶，当 \(h\) 比较大的时候，这显然是无法接受的。但从这个角度想就给了我们解决问题的突破口：由于每个数 \(+1\) 的总次数是 \(O(n)\) 的，因此如果设个阈值 \(B=2^k\)，那么它在 \(2^k\) 以上的位进位次数其实是 \(\dfrac{n}{2^k}\) 的，这启发我们根号分治。
具体来说，我们每个块内部维护一个桶 \(buc_{b,i,j}\)，其中 \(b\) 表示块编号，\(buc_{b,i,j}\) 表示第 \(b\) 块中有多少个数 \(\bmod 2^i=j\)，这样修改时候，碰到散块就暴力 pushdown 然后重构，碰到整块 \(+1\) 时候，对于 \(\le 2^k\) 的位，我们就调用预处理的 \(buc_{b,i,j}\) 来在 \(O(k2^k)\) 计算这次修改对全局异或和的影响。对于 \(>2^k\) 的位，显然这只会发生在当前 \(b_j\equiv 2^{k}-1\pmod{2^k}\) 的 \(j\) 上，我们提前在重构的时候对每个 \(i\in[0,2^k-1]\) 预处理出 \(b_j\equiv i\pmod{2^k}\) 的 \(j\) 组成的集合，然后暴力改即可，根据上面的分析，这部分复杂度是均摊 \(O(\dfrac{n}{2^k})\)。
这样实现时间复杂度为 \(O(n\sqrt{n}\log n)\)，可以获得 60 分，代码如下，应该写的很清楚：
const int MAXN=4e5;
const int blk_sz=256;
const int LOG_B=8;
int n,qu,lst[MAXN+5],a[MAXN+5],bel[MAXN+5];
int res[MAXN+5],ql[MAXN+5],qr[MAXN+5];
vector<pii>qv[MAXN+5];
struct block{
int L,R,len,b[blk_sz+5],c[2][blk_sz+5],tag,tot_xor[2];
int mark[2][LOG_B+1][blk_sz+2],cnt[LOG_B+1][blk_sz+2];
vector<int>vec[blk_sz+2];
void init(){
tag=0;
memset(mark,0,sizeof(mark));memset(cnt,0,sizeof(cnt));
for(int j=0;j<LOG_B;j++)cnt[j][0]=len;
for(int j=0;j<blk_sz;j++)vec[j].clear();
for(int j=1;j<=len;j++)vec[0].pb(j);
}
void add(int tim,int ql,int qr){
for(int o=0;o<2;o++)for(int k=1;k<=len;k++)for(int t=0;t<LOG_B;t++)
c[o][k]^=mark[o][t][b[k]&((1<<t+1)-1)];
for(int k=1;k<=len;k++)b[k]+=tag;
for(int k=ql;k<=qr;k++){
c[tim][k]^=(b[k]^(b[k]+1));
tot_xor[tim]^=(b[k]^(b[k]+1));
++b[k];
}
tag=0;
memset(mark,0,sizeof(mark));memset(cnt,0,sizeof(cnt));
for(int k=1;k<=len;k++)for(int t=0;t<LOG_B;t++)
cnt[t][b[k]&((1<<t+1)-1)]++;
for(int k=0;k<blk_sz;k++)vec[k].clear();
for(int k=1;k<=len;k++)vec[b[k]&(blk_sz-1)].pb(k);
}
void addwhole(int tim){
for(int t=0;t<LOG_B;t++){
int val=((1<<t)-1-tag)&((1<<t+1)-1);
mark[tim][t][val]^=((1<<t+1)-1);
if(cnt[t][val]&1)tot_xor[tim]^=((1<<t+1)-1);
}
for(int p:vec[(blk_sz-1-tag)&(blk_sz-1)]){
c[tim][p]^=(b[p]+tag)^(b[p]+tag+1);
tot_xor[tim]^=(b[p]+tag)^(b[p]+tag+1);
}
tag++;
}
int query(int tim,int ql,int qr){
int res=0;
for(int k=ql;k<=qr;k++){
res^=c[tim][k];
for(int t=0;t<LOG_B;t++)
res^=mark[tim][t][b[k]&((1<<t+1)-1)];
}return res;
}
int querywhole(int tim){return tot_xor[tim];}
}B[MAXN/blk_sz+5];
int main(){
scanf("%d%d",&n,&qu);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1,l,r;i<=qu;i++){scanf("%d%d",&l,&r);qv[r].pb(mp(l,i));}
for(int i=1;i<=n;i++)ql[i]=lst[a[i]]+1,qr[i]=i,lst[a[i]]=i;
int blk_cnt=(n-1)/blk_sz+1;
for(int i=1;i<=blk_cnt;i++){
int L=(i-1)*blk_sz+1,R=min(i*blk_sz,n);
B[i].L=L;B[i].R=R;B[i].len=R-L+1;
for(int j=L;j<=R;j++)bel[j]=i;
B[i].init();
}
for(int i=1;i<=n;i++){
int L=ql[i],R=qr[i];
if(bel[L]==bel[R]){
B[bel[L]].add(i&1,L-B[bel[L]].L+1,R-B[bel[L]].L+1);
}else{
B[bel[L]].add(i&1,L-B[bel[L]].L+1,B[bel[L]].len);
B[bel[R]].add(i&1,1,R-B[bel[R]].L+1);
for(int j=bel[L]+1;j<bel[R];j++)B[j].addwhole(i&1);
}
for(pii p:qv[i]){
L=p.fi;R=i;
if(bel[L]==bel[R]){
res[p.se]=B[bel[L]].query(i&1,L-B[bel[L]].L+1,R-B[bel[L]].L+1);
}else{
res[p.se]^=B[bel[L]].query(i&1,L-B[bel[L]].L+1,B[bel[L]].len);
res[p.se]^=B[bel[R]].query(i&1,1,R-B[bel[R]].L+1);
for(int j=bel[L]+1;j<bel[R];j++)res[p.se]^=B[j].querywhole(i&1);
}
}
}
for(int i=1;i<=qu;i++)printf("%d\n",res[i]);
return 0;
}
考虑优化，发现不太牛的地方在于我们处理 \(\le 2^k\) 的部分我们要遍历每一位并考虑其作为 \(h\) 的情况。考虑稍微改变下维护方法，我们在预处理的时候提前处理出 \(coef_{tag}\) 表示这块中所有 \((b_i+tag)\oplus(b_i+tag+1)\) 的异或和对 \(2^k\) 取模的结果 \((tag\in[0,2^k-1])\)，如果我们能高效求出这个，那么我们就能 \(O(1)\) 地求出一次整块加一中 \(\le 2^k\) 的那部分对答案的贡献。考虑如何求之，记 \(cnt_i\) 为 \(b_j=i\) 的个数 \(\bmod 2\)，那么稍微变下形可知，如果记 \(l=2^k-tag-1\)，那么 \(coef_{tag}=\operatorname{\oplus}\limits_{t=0}^{k-1}\operatorname{\oplus}\limits_{k\equiv l\pmod{2^k}}2^t·cnt_l\)。考虑如何高效做这个变换，我们从低位向高位考虑这个 \(t\)，我们发现，考虑到第 \(t\) 位的时候，所有 \(\bmod 2^k\) 相同的 \(l\) 的 \(coef_l\) 值都是相同的，这样我们相当于只用维护 \(2^0+2^1+\cdots+2^k=2^{k+1}-1\) 个值（可以像完全二叉树那样编号，这样不用开 vector，常数会小很多）。而从 \(t\) 推到 \(t+1\) 的时候我们需要知道 \(f_{t,k}=\operatorname\oplus_{k\equiv l\pmod{2^k}}cnt_l\)，这同样可以用类似的类二叉树方法维护，不过底层元素需要像 FFT 那样做一个 butterfly 变换，具体实现代码中 trans 的部分，于是这部分复杂度被我们成功降到了 \(O(2^k)\)，这样复杂度就是 \(O(n\sqrt{n})\)，可以获得 100 分。
最后是最终代码，个别细节与上文所述略有区别，不过感觉无伤大雅。
const int MAXN=4e5;
const int blk_sz=256;
const int LOG_B=8;
int n,qu,lst[MAXN+5],a[MAXN+5],bel[MAXN+5],dep[blk_sz*2+5],rev[blk_sz+5];
int res[MAXN+5],ql[MAXN+5],qr[MAXN+5];
vector<pii>qv[MAXN+5];
struct block{
int L,R,len,b[blk_sz+5],c[2][blk_sz+5],tag,tot_xor[2];
int coef[blk_sz+5],tot[2][blk_sz+5],nw[blk_sz+5];
vector<int>vec[blk_sz+2];
void trans(int *f,int *g){
static int A[blk_sz*2+5],B[blk_sz*2+5];
for(int i=0;i<blk_sz;i++)A[rev[i]|blk_sz]=f[i];
for(int i=blk_sz-1;i;i--)A[i]=A[i<<1]^A[i<<1|1];
for(int i=1;i<=blk_sz*2-1;i++)B[i]=B[i>>1]^(A[i]<<dep[i]);
for(int i=0;i<blk_sz;i++)g[i]=B[rev[i]|blk_sz]^(f[i]*(blk_sz*2-1));
}
void pushdown(){
if(!tag)return;
for(int o=0;o<2;o++){
trans(tot[o],nw);
for(int k=1;k<=len;k++)c[o][k]^=nw[b[k]&(blk_sz-1)];
}
memset(tot,0,sizeof(tot));
for(int k=1;k<=len;k++)b[k]+=tag;
tag=0;
}
void rebuild(){
for(int k=0;k<blk_sz;k++)vec[k].clear();
for(int k=1;k<=len;k++)vec[b[k]&(blk_sz-1)].pb(k);
memset(coef,0,sizeof(coef));
static int tmp[blk_sz+5];
for(int k=0;k<blk_sz;k++)tmp[k]=vec[k].size()&1;
trans(tmp,coef);
}
void init(){tag=0;rebuild();}
void add(int tim,int ql,int qr){
pushdown();
for(int k=ql;k<=qr;k++){
c[tim][k]^=(b[k]^(b[k]+1));
tot_xor[tim]^=(b[k]^(b[k]+1));
++b[k];
}
rebuild();
}
void addwhole(int tim){
int val=(blk_sz-1-tag)&(blk_sz-1);
tot_xor[tim]^=coef[val];
tot[tim][val]^=1;
for(int p:vec[val]){
c[tim][p]^=(b[p]+tag)^(b[p]+tag+1);
tot_xor[tim]^=(b[p]+tag)^(b[p]+tag+1);
}
tag++;
}
int query(int tim,int ql,int qr){
if(tag)pushdown(),rebuild();
int res=0;
for(int k=ql;k<=qr;k++)res^=c[tim][k];
return res;
}
int querywhole(int tim){return tot_xor[tim];}
}B[MAXN/blk_sz+5];
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&qu);
for(int i=0;i<blk_sz;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(LOG_B-1));
for(int i=2;i<blk_sz*2;i++)dep[i]=dep[i>>1]+1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1,l,r;i<=qu;i++){scanf("%d%d",&l,&r);qv[r].pb(mp(l,i));}
for(int i=1;i<=n;i++)ql[i]=lst[a[i]]+1,qr[i]=i,lst[a[i]]=i;
int blk_cnt=(n-1)/blk_sz+1;
for(int i=1;i<=blk_cnt;i++){
int L=(i-1)*blk_sz+1,R=min(i*blk_sz,n);
B[i].L=L;B[i].R=R;B[i].len=R-L+1;
for(int j=L;j<=R;j++)bel[j]=i;
B[i].init();
}
for(int i=1;i<=n;i++){
int L=ql[i],R=qr[i];
if(bel[L]==bel[R]){
B[bel[L]].add(i&1,L-B[bel[L]].L+1,R-B[bel[L]].L+1);
}else{
B[bel[L]].add(i&1,L-B[bel[L]].L+1,B[bel[L]].len);
B[bel[R]].add(i&1,1,R-B[bel[R]].L+1);
for(int j=bel[L]+1;j<bel[R];j++)B[j].addwhole(i&1);
}
for(pii p:qv[i]){
L=p.fi;R=i;
if(bel[L]==bel[R]){
res[p.se]=B[bel[L]].query(i&1,L-B[bel[L]].L+1,R-B[bel[L]].L+1);
}else{
res[p.se]^=B[bel[L]].query(i&1,L-B[bel[L]].L+1,B[bel[L]].len);
res[p.se]^=B[bel[R]].query(i&1,1,R-B[bel[R]].L+1);
for(int j=bel[L]+1;j<bel[R];j++)res[p.se]^=B[j].querywhole(i&1);
}
}
}
for(int i=1;i<=qu;i++)printf("%d\n",res[i]);
return 0;
}