[杭电多校2 | HDUOJ]7152.Copy(DP + Bitset + 思维)

发布于 2022-07-21  630 次阅读


题目链接: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;
}