题目链接: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; }
Comments 1 条评论
Eriktse聚聚 :drooling: :drooling: