题解：P10009 [集训队互测 2022] 线段树
MatrixGroup
·
·
题解
题意
给定一个长度为 n 的序列。有 q 次操作，每次操作形如区间替换为异或差分或者单点求值。最后还要输出整个序列。
## 题解
稍微思考一下可以发现这个不太线段树可维护，因为前面的东西可能会很大程度上影响到后面的东西。但是有一个比较好的性质是 $t$ 次修改后影响的元素最多距离是 $d$。由此可以考虑定期重构：对操作每 $B$ 个一组处理，序列每 $B$ 个分一块，则每一组操作的块只有块内和相邻的块会有影响。
首先考虑如何处理整块的 tag。稍作分析可以得到贡献是组合数，因为异或只需要考虑奇偶性，因此 $q$ 次整体做差分后，$a_i$ 会变成 $a_{i-c}$ 的异或和，其中 $c$ 在二进制下是 $q$ 的子集。换言之，为了重构，只需对于 $q$ 的每个非零位 $2^j$，每隔 $2^j$ 个做一次差分即可。这样重构一个块的复杂度不超过 $O(B\log q)$。
为了方便，每 $B$ 次操作对于每个相邻的两块考虑，再遍历这 $B$ 个操作。询问就直接枚举子集，而修改如果当前两块**都**是整块就增加 tag 的值，否则按照上述方法重构再暴力做。最后处理完所有的 $B$ 次操作记得再重构一下。
分析一下复杂度。查询的复杂度是枚举子集，不超过 $O(qB)$，而每次涉及的散块重构复杂度是 $O(qB\log q)$，而每组询问最后重构复杂度一共是 $O\left(\dfrac qBn\log q\right)$。取 $B=\Theta(\sqrt n)$，总时间复杂度 $O(n+q\sqrt n\log q)$。
## 代码
非常好写！
```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
using namespace std;
int orn;
const int B=512;
int subid,n,q,a[252005],c,b[252005],res[252005];
int tp[252005],l[252005],r[252005],ans[252005];
void solve(int *arr,int L,int R,int x)
{
rep(i,20) if((x>>i)&1)
{
for(int j=R-(1<<i),k=R;j>=L;--j,--k) arr[k]^=arr[j];
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>subid;
cin>>n>>q;
rep(i,n)
{
cin>>a[i];
}
orn=n;
while(n%B)++n;
rep(i,q)
{
cin>>tp[i]>>l[i];
if(tp[i]==1)
{
cin>>r[i];--r[i];
}
else
{
--l[i];
}
}
rep(_,q/B+1)
{
for(int i=0;i<n/B;++i)
{
c=0;
int lb=i*B,rb=(i+1)*B-1,lb0=max(0,lb-B);
memcpy(b+lb0,a+lb0,sizeof(int)*(rb-lb0+1));
for(int j=_*B;j<(_+1)*B&&j<q;++j)
{
if(tp[j]==1)
{
if(l[j]<=lb0&&rb<=r[j])
{
++c;
}
else if(!(r[j]<lb0||l[j]>rb))
{
solve(b,lb0,rb,c);
c=0;
for(int k=min(r[j],rb);k>=max(lb0+1,l[j]);--k) b[k]^=b[k-1];
}
}
else if(lb<=l[j]&&l[j]<=rb)
{
int idx=l[j],ret=0;
for(int cur=65536;cur;)
{
cur=(cur-1)&c;
if(idx-cur>=0)
{
ret^=b[idx-cur];
}
}
ans[j]=ret;
}
}
solve(b,lb0,rb,c);
memcpy(res+lb,b+lb,sizeof(int)*B);
}
memcpy(a,res,sizeof(int)*n);
}
rep(i,q) if(tp[i]==2) cout<<ans[i]<<'\n';
rep(i,orn) cout<<a[i]<<'\n';
return 0;
}
```