题解：P10009 [集训队互测 2022] 线段树

题意

给定一个长度为

n

的序列。有

q

次操作，每次操作形如区间替换为异或差分或者单点求值。最后还要输出整个序列。

n\le 2.5\times 10^5,q\le 10^5

，3s。

题解

稍微思考一下可以发现这个不太线段树可维护，因为前面的东西可能会很大程度上影响到后面的东西。但是有一个比较好的性质是

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;
}

题解：P10009 [集训队互测 2022] 线段树

文章操作

题意

题解

代码

相关推荐

评论

题解：P10009 [集训队互测 2022] 线段树