Treap (making range queries(that are not possible on seg_Trees) possible with no effort) : (863D), C++ (gcc)

Treap (making range queries(that are not possible on seg_Trees) possible with no effort) : (863D)

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

struct Treap{
    struct node{
        int val, rev, cnt;
        ll prior;
        node *l, *r;
        
        node(ll p, int v, node *lft = NULL, node* rgt = NULL) : val(v), prior(p), l(lft), r(rgt), rev(0){}
    };
    
    typedef node* pnode;
    
    int get_cnt(pnode r){
        return r? r -> cnt : 0;
    }
    
    void upd_(pnode r){
        if(r) r -> cnt = get_cnt(r -> l) + get_cnt(r -> r) + 1;
    }
    
    void push(pnode r){
        if(r && r -> rev){
            if(r -> l) r -> l -> rev ^= 1;
            if(r -> r) r -> r -> rev ^= 1;
            swap(r -> l, r -> r);
            r -> rev = 0;
        }
    }
    
    void split(pnode root, pnode& l, pnode &r, int ind){
        if(!root) return void(l = r = NULL);
        push(root);
        
        int cur = get_cnt(root -> l) + 1;
        if(ind >= cur) split(root -> r, root -> r, r, ind-cur), l = root;
        else split(root -> l, l, root -> l, ind), r = root;
        upd_(root);
    }
    
    void merge(pnode& root, pnode l, pnode r){
        push(l), push(r);
        if(!l || !r) return void(root = l? l : r);
        
        if(l -> prior > r -> prior) merge(l -> r, l -> r, r), root = l;
        else merge(r -> l, l, r -> l), root = r;
        upd_(root);
    }
    
    void insert(int pos, int val){
        ll p = rand();
        pnode cur = new node(p, val);
        cur -> cnt = 1;
        
        pnode l, r;
        split(root, l, r, pos-1);
        merge(l, l, cur);
        merge(root, l, r);
    }
    
    void query1(int l, int r){
        if(l == r) return;
        
        pnode t1, t2, t3, t4;
        split(root, t1, t2, l-1);
        split(t2, t2, t3, r-1-(l-1));
        split(t3, t3, t4, r - (r - 1));
        
        merge(t1, t1, t3);
        merge(t1, t1, t2);
        merge(root, t1, t4);
    }
    
    void query2(int l, int r){
        if(l == r) return;
        
        pnode t1, t2, t3;
        split(root, t1, t2, l-1);
        split(t2, t2, t3, r - (l-1));
        
        /*cout << "query2 : " << l << " " << r << " : " << endl;
        cout << "t1 : "; print(t1);
        cout << "t2 : "; print(t2);
        cout << "t3 : "; print(t3);
        cout << endl;*/
        
        t2 -> rev ^= 1;
        
        merge(t2, t2, t3);
        merge(root, t1, t2);
    }
    
    int get(int pos){
        pnode t1, t2, t3;
        split(root, t1, t2, pos-1);
        split(t2, t2, t3, pos - (pos - 1));
        
        int ans = t2 -> val;
        
        merge(t2, t2, t3);
        merge(root, t1, t2);
        return ans;
    }
    
    void print(pnode r){
        if(r){
            print(r -> l);
            cout << r -> val << " ";
            print(r -> r);
        }
    }
    
    void print(){
        print(root);
        cout << endl;
    }
    
    Treap() : root (NULL){}
    
    private :
        pnode root;
};

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int n, q, m;
    scanf("%d %d %d",&n ,&q ,&m);
    Treap tp;
    
    for(int j = 1; j <= n; j++){
        int c;
        scanf("%d",&c);
        tp.insert(j, c);
    }
    //tp.print();
    
    while(q--){
        int t, l, r;
        scanf("%d %d %d",&t ,&l, &r);
        if(t == 1) tp.query1(l, r);
        else tp.query2(l, r);
        //tp.print();
    }
    
    vector<int> a(n+1, -1);
    while(m--){
        int x;
        scanf("%d",&x);
        if(a[x] == -1) a[x] = tp.get(x);
        printf("%d ",a[x]);
    }
    return 0;
}


run \| edit \| history \| help	0