Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int const inf = 1e9;
- typedef struct item * pitem;
- struct item
- {
- int prior, value, cnt, fun;
- pitem l, r;
- int p;
- item(){}
- };
- pitem tree;
- int cnt (pitem it){
- return it ? it -> cnt : 0;
- }
- void upd_cnt(pitem it){
- if(it)
- it -> cnt = cnt(it -> l) + cnt(it -> r) + 1;
- }
- int fun(pitem it){
- return it ? it -> fun : 0;
- }
- void upd_fun(pitem it){
- if(it)
- // it -> fun = max(it -> value, max(fun(it -> r), fun(it -> l)));
- it -> fun = fun(it -> l) + fun(it -> r) + it -> value;
- }
- void push(pitem it){
- if(it && it -> p){
- int p = it -> p;
- it -> p = 0;
- it -> value += p;
- // upd_fun(it);
- if (it->l) it->l-> p = p;
- if (it->r) it->r-> p = p;
- }
- }
- void merge(pitem & t, pitem l, pitem r){
- push(l);
- push(r);
- if(!l || !r)
- return void ( t = l ? l : r);
- if(l -> prior > r -> prior){
- merge(l -> r, l -> r, r), t = l;
- }
- else{
- merge(r -> l, l, r -> l), t = r;
- }
- upd_cnt(t);
- upd_fun(t);
- }
- void split(pitem t, pitem &l, pitem &r, int key, int add = 0){
- if(!t)
- return void(l = r = 0);
- push(t);
- int cur_key = add + cnt(t -> l);
- if(key <= cur_key)
- split(t -> l, l, t -> l, key, add), r = t;
- else
- split(t -> r, t-> r, r, key, add + 1 + cnt(t -> l)), l = t;
- upd_cnt(t);
- upd_fun(t);
- }
- pitem new_pitem(int val){
- pitem t = new item;
- t -> value = val;
- t -> fun = val;
- t -> l = 0;
- t -> r = 0;
- t -> prior = rand();
- t -> cnt = 1;
- t -> p = 0;
- return t;
- }
- void output (pitem t) {
- if (!t) return;
- push(t);
- output (t->l);
- printf ("%d ", t->value);
- output (t->r);
- }
- int otr_fun(pitem t, int a, int b){
- pitem t1, t2;
- split(t, t, t1, a);
- split(t1, t1, t2, b - a + 1);
- int ans = t1 -> fun;
- merge(tree, tree, t1);
- merge(tree, tree, t2);
- return ans;
- }
- void add(pitem &t, int x, int pos){
- pitem t1, ad;
- split(t, t, t1, pos);
- ad = new_pitem(x);
- merge(t, t, ad);
- merge(t, t, t1);
- }
- void del(pitem &t, int pos){
- pitem t1, del;
- split(t, t, del, pos);
- split(del, del, t1, 1);
- merge(t, t, t1);
- output(t);
- }
- void upd(pitem &t, int pos, int x){
- pitem t1, nw;
- split(t, t, nw, pos);
- split(nw, nw, t1, 1);
- nw -> value = x;
- upd_fun(nw);
- merge(t, t, nw);
- merge(t, t, t1);
- }
- void otr_upd(pitem &t, int a, int b, int x){
- pitem t1, t2;
- split(t, t, t1, a);
- split(t1, t1, t2, b - a + 1);
- t1 -> p = x;
- push(t1);
- merge(t, t, t1);
- merge(t, t, t2);
- }
- int main(){
- freopen("in.txt", "r", stdin);
- int n;
- cin >> n;
- for(int i = 0; i < n; i++){
- int a;
- cin >> a;
- pitem t1 = new_pitem(a);
- merge(tree, tree, t1);
- // output(tree);
- // cout << endl;
- }
- otr_upd(tree,1, 3, 55);
- output(tree);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement