CSAcademy：Strings

CSAcademy：Strings

題目大意：給一個字串，有三種操作，$f_1, f_2, f_3$。$f_1(i, j, k)$：將字串分成 $S[1\sim i-1], S[i\sim j], S[j+1\sim size(S)]$，將第一部分與第三部分組成 $T$，將 $T$ 分成 $T[1\sim k], T[k+1\sim size(T)]$，再將 $S = T_1 + S + T_2$。$f_2(i, j)$：將 $S[i, j]$ 反轉。$f_3(i, c)$：在 $S[i-1]$ 和 $S[i]$ 間插入 $c$。詢問時會給 $i,j$，問 $S[i\sim j]$ 是否是回文。

解法：很顯然是 $\text{treap} + \text{hash}$，只是實作有點麻煩。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

#define null NULL
#define Size(x) (x?x->siz:0)
#define rnd(l,r) uniform_int_distribution<int>(l,r)(seed)
mt19937 seed (time (NULL));

const int base = 137;
const int MOD = 1e9 + 7;
const int SIZE = 5e5;

int hs[SIZE + 5];

struct Node {
    int siz = 1, prior = rnd (1, 2e9), lh = 0, rh = 0;
    bool rev = 0;
    char c;
    Node *ls = null, *rs = null;
    Node() {}
    Node (char cc) : c (cc), lh (cc), rh (cc) {}
};

void Push (Node *node) {
    if (!node) {
        return;
    }
    if (node->rev) {
        swap (node->lh, node->rh);
        swap (node->ls, node->rs);
        if (node->ls) {
            node->ls->rev ^= 1;
        }
        if (node->rs) {
            node->rs->rev ^= 1;
        }
        node->rev = 0;
    }
}

void Pull (Node *a) {
    Push (a->ls), Push (a->rs);
    a->siz = Size (a->ls) + Size (a->rs) + 1;
    a->lh = a->ls ? a->ls->lh : 0;
    a->lh = (1ll * a->lh * hs[1] + a->c) % MOD;
    a->lh = ( (1ll * a->lh * hs[Size (a->rs)]) + (a->rs ? a->rs->lh : 0)) % MOD;
    a->rh = a->rs ? a->rs->rh : 0;
    a->rh = (1ll * a->rh * hs[1] + a->c) % MOD;
    a->rh = ( (1ll * a->rh * hs[Size (a->ls)]) + (a->ls ? a->ls->rh : 0)) % MOD;
}

Node *Merge (Node *a, Node *b) {
    if (!a || !b) {
        return a ? a : b;
    }
    if (a->prior > b->prior) {
        Push (a);
        a->rs = Merge (a->rs, b);
        Pull (a);
        return a;
    } else {
        Push (b);
        b->ls = Merge (a, b->ls);
        Pull (b);
        return b;
    }
}

void Split (Node *node, Node *&a, Node *&b, int k) {
    if (!node) {
        a = b = null;
        return;
    }
    Push (node);
    if (Size (node->ls) >= k) {
        b = node;
        Split (node->ls, a, b->ls, k);
        Pull (b);
    } else {
        a = node;
        Split (node->rs, a->rs, b, k - Size (node->ls) - 1);
        Pull (a);
    }
}

int n, q;
string s;

void solve() {
    hs[0] = 1;
    FOR (i, 1, SIZE) hs[i] = 1ll * hs[i - 1] * base % MOD;
    cin >> n >> q >> s;
    Node *T = null;
    for (char c : s) {
        T = Merge (T, new Node (c));
    }
    while (q--) {
        char ty, c;
        cin >> ty;
        int l, r, k, t;
        if (ty == 'Q') {
            cin >> l >> r;
            Node *T1, *T2;
            Split (T, T, T2, r);
            Split (T, T1, T, l - 1);
            cout << (T->lh == T->rh ? "YES\n" : "NO\n");
            T = Merge (Merge (T1, T), T2);
        } else {
            cin >> t;
            if (t == 1) {
                cin >> l >> r >> k;
                Node *T1, *T2;
                Split (T, T, T2, r);
                Split (T, T1, T, l - 1);
                T1 = Merge (T1, T2);
                Split (T1, T1, T2, k);
                T = Merge (Merge (T1, T), T2);
            } else if (t == 2) {
                cin >> l >> r;
                Node *T1, *T2;
                Split (T, T, T2, r);
                Split (T, T1, T, l - 1);
                T->rev ^= 1;
                T = Merge (Merge (T1, T), T2);
            } else {
                cin >> l >> c;
                Node *T1;
                Split (T, T1, T, l - 1);
                T = Merge (Merge (T1, new Node (c)), T);
            }
        }
    }
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！