Submission #1325688

#TimeUsernameProblemLanguageResultExecution timeMemory
1325688aaaaaaaaCollider (IZhO11_collider)C++20
100 / 100
124 ms48376 KiB
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct node{
    node *left, *right;
    int sz, pri, val;
    node(int x){
        left = right = nullptr;
        sz = 1, val = x, pri = rnd();
    }
} *root;
int get_sz(node *curr){
    if(!curr) return 0;
    int x = 1;
    if(curr -> left) x += curr -> left -> sz;
    if(curr -> right) x += curr -> right -> sz;
    return x;
}
void pull(node *& curr){
    curr -> sz = get_sz(curr);
}
void split(node *root, int x, node *&left, node *&right){
    if(!root){
        left = right = nullptr;
        return;
    }
    if(get_sz(root -> left) < x){
        split(root -> right, x - get_sz(root -> left) - 1, root -> right, right);
        left = root;
    }else{
        split(root -> left, x, left, root -> left);
        right = root;
    }
    pull(root);
}
void merge(node *& root, node *left, node *right){
    if(!left || !right){
        root = left ? left : right;
        return;
    }
    if(left -> pri > right -> pri){
        merge(left -> right, left -> right, right);
        root = left;
    }else{
        merge(right -> left, left, right -> left);
        root = right;
    }
    pull(root);
}
void update(int l, int r){
    node *a, *b, *c, *d, *e, *f;
    split(root, l - 1, a, b);
    split(b, 1, c, d);
    merge(a, a, d);
    split(a, r - 1, e, f);
    merge(e, e, c);
    merge(e, e, f);
    root = e;
}
int query(node *cur, int idx){
    if(cur == nullptr) return 0;
    int left_sz = get_sz(cur->left);
    if(idx == left_sz + 1) return cur->val;
    if(idx <= left_sz) return query(cur->left, idx);
    else return query(cur->right, idx - left_sz - 1);
}
int query(int x){
    return query(root, x);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, q, l, r;
    string str;
    cin >> n >> q >> str;
    for(int i = 0; i < n; ++i){
        merge(root, root, new node(str[i] - 'a'));
    }
    while(q--){
        char type;
        cin >> type;
        if(type == 'a'){
            cin >> l >> r;
            update(l, r);
        }else{
            cin >> l;
            cout << (char) (query(l) + 'a') << "\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...