CF1878D Reverse Madness

LCat90 · 2023-10-08 23:50:29 · 题解

一种暴力的做法是平衡树无脑翻转。

但是我们考虑巧妙的做法。题目中 x 对应了一个连续的区间，并且这些区间一定没有交叉，要么就是包含。

根据这个性质，对于一个点 i，我们记录它被翻转了几次。如果是奇数次，就将它和另一个元素翻转；如果偶数次则保留。区间加我们可以维护差分序列，最后求和。

如果预处理出 x 对应的区间的话时间复杂度就是 O(n+q)。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int t, n, q, a[N], k, ans, pre[N];
int read(); char c[N]; bool vis[N];
struct node {
    int l, r;
    friend bool operator < (node a, node b) {
        return a.l < b.l;
    }
} p[N];
signed main() {
    cin >> t;
    while(t--) { 
        cin >> n >> k; 
        scanf("%s", c + 1);
        for(int i = 1;i <= k; ++i) scanf("%d", &p[i].l);
        for(int i = 1;i <= k; ++i) scanf("%d", &p[i].r);
        for(int i = 1;i <= n; ++i) vis[i] = a[i] = pre[i] = 0;
        sort(p + 1, p + k + 1);
        cin >> q;
        while(q--) { int x;
            scanf("%d", &x);
            int l = 1, r = k;
            while(l < r) {
                int mid = l + r >> 1;
                if(p[mid].r >= x) r = mid;
                else l = mid + 1;
            }

            int L = min(x, p[l].r + p[l].l - x), R = max(x, p[l].r + p[l].l - x);
//          cout << "\n" << l << " " << L << " " << R << "\n\n";
            pre[L] ++; pre[R + 1] --;
        }
        for(int i = 1;i <= n; ++i) a[i] = a[i - 1] + pre[i]; int cnt = 1;
//      for(int i = 1;i <= n; ++i) cout << a[i] << " "; puts("");
        for(int i = 1;i <= n; ++i) {
            if(i > p[cnt].r) cnt ++;
            if(a[i] & 1) {
                if(vis[i]) continue ;
                vis[i] = vis[p[cnt].r - i + p[cnt].l] = 1;
                swap(c[i], c[p[cnt].r - i + p[cnt].l]);
            }
        }
        for(int i = 1;i <= n; ++i) cout << c[i];
        puts("");
    }  
    return 0;
}

/*

*/

int read() {
    char c; int sum = 0; while(c < '0' or c > '9') c = getchar();
    while(c >= '0' and c <= '9') sum = (sum << 3) + (sum << 1) + (c ^ 48), c = getchar();
    return sum; 
}