题目链接：Problem - 7152 (hdu.edu.cn)

题目 / Problem

有T个测试用例。

给定一个长度为N的数组，进行Q次操作。

每次操作有两种模式，模式1：选择一个区间[l, r]，将其复制一份并插入到这个区间右端点的后面，大于N的部分自动剔除。模式2：查询当前数组第x位的元素。

求所有操作模式2的查询结果的异或和。

思路 / Thought

我直呼牛逼！

首先不难想到，当进行操作1之后，后面的所有操作2都会受到影响。

具体影响为：若x <= r则没有影响，若x > r则x -= (r - l + 1)，也就是说后面查询新数组的下标x的元素，应该返回原数组的下标x - (r - l + 1)的元素。

也就是每遇到一个操作1，就要把后面（右边）的所有的x都进行一次更新，前面的（左边的）当然不受影响。这样复杂度是O(N ^ 2)，显然无法接受。

于是可以考虑用bitset优化，正好考虑到这里求的是所有操作2结果的异或和，我们用一个bitset<maxn> dp来表示原数组的某一位是否需要异或（异或具有抵消性质）。

那么当我们遇到操作2的时候就dp[x] ^= 1，将x位异或一下，遇到操作1就更新后面的所有x。但是这样复杂度并没有变，因为没有用到bitset的优化，那么怎么用呢，bitset优化一般是直接对bitset进行位运算，这里从前往后是不能进行位运算的，需要从后往前。

具体方法是：将所有操作离线保存，然后从后往前，当遇到x就dp[x] = dp[x] ^ 1，（注意dp[x] ^= 1可能会编译错误）,遇到操作1就通过位运算来移动dp这个bitset，x -= (r - l + 1)也就是x >> (r - l + 1)，这个只需要在x > r的时候操作，所以对dp进行一次分解 - 移动 - 重组就好了。这样就通过N / w的复杂度对N个数据进行了移动。

值得注意的是，在bitset中，最右侧的是第0位，从右往左依次递增，所以x减小应该右移。

最后遍历一下dp，将对应位置的元素异或一下就好了。

我直呼牛逼！

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int a[maxn];

struct OP
{
	int op, l, r, x;
};

void solve()
{
	int N, Q;cin >> N >> Q;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	
	vector<OP> v;
	bitset<maxn> dp;
	//离线保存 
	while(Q --)
	{
		int op;cin >> op;
		if(op == 1)
		{
			int l, r;cin >> l >> r;
			v.push_back({1, l, r, 0});
		}else if(op == 2)
		{
			int x;cin >> x;
			v.push_back({2, 0, 0, x});
		}
	}
	
	for(int i = v.size() - 1;i >= 0; -- i)
	{
		if(v[i].op == 1)
		{
			int l = v[i].l, r = v[i].r;
			//用纸画一下bitset的二进制位表示，就很好写了 
			//bitset从右往左表示 
			bitset<maxn> low  = dp & (~bitset<maxn>(0) >> (maxn - 1 - r));
			bitset<maxn> high = dp & (~bitset<maxn>(0) << (r + 1));
			dp = low ^ (high >> (r - l + 1));	
		}
		else
		{
			int x = v[i].x;
			dp[x] = dp[x] ^ 1;
		}
	}
	
	int ans = 0;
	for(int i = 1;i <= N; ++ i)if(dp[i])ans ^= a[i];
	cout << ans << '\n';
}


signed main()
{
	ios::sync_with_stdio(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}