2022杭电多校2 C Copy

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7152

简要题意：给定一个长度为 $n$ 的序列 $a_i$，以及 $m$ 次操作，操作有两种，第一种是给定一个区间 $[l,r]$，将 $[l,r]$ 中的数复制一份放到 $[l,r]$ 的后面，并将其他数后移；第二种操作是给定一个 $x$，查询 $a_x$，最后输出所有查询的异或和

$n,m\le 10^5$，保证第一种操作的个数小于等于 $20000$

Solution

我们考虑将操作离线，注意到对于一次一操作 $[l,r]$ 之后的查询 $x$，如果 $x>r$，那么我们相当于将 $x$ 变成 $x-(r-l+1)$，对于 $x\le r$，则无影响，同时我们注意到只需要输出所有查询的异或和，那么我们可以用 $bitset$ 维护每个位置是否出现，同时 $bitset$ 可以通过左移和右移简单完成一操作

#include <iostream>
#include <bitset>
#define maxn 100010
#define ll long long
using namespace std;

const int N = 100001;

int n, m, a[maxn];

struct Query {
    int opt, x, y;
} Q[maxn];

void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i].opt >> Q[i].x;
        if (Q[i].opt == 1) cin >> Q[i].y;
    } bitset<N> B, low, high;
    for (int i = m; i; --i) {
        int opt = Q[i].opt, x = Q[i].x, y = Q[i].y;
        if (opt == 1) {
            low = B & ~bitset<N>(0) >> N - y - 1;
            high = B & ~bitset<N>(0) << y + 1;
            B = low ^ high >> y - x + 1; 
        } else B.flip(x);
    } int ans = 0;
    for (int i = 1; i <= n; ++i) if (B[i]) ans ^= a[i];
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}