Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
UnghiLansator
133
c2p
data locality - fast example
Power of an element
DP Optimization another kind
Sort row sorted matrix
DoubleListInt
TempBubbleDouble
sin_approximation