(POJ) 3580 -- SuperMemo

http://poj.org/problem?id=3580

終於AC了！！！

其實我覺得我寫的這樣不太好，因為我存了正常的序列 + 反序列(只是為了要reverse)

之後應該會補上有reverse當tag的版本

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAX_N = 2e5 + 6;
const int MAX_M = 1e5 + 6;
const LL INF = 1e17 + 6;

struct Treap {
 Treap *lc;
 Treap *rc;
 LL val;
 int sz;
 LL tag;
 LL mn;
 int pri;
 Treap(LL _val) {
     lc=rc=NULL;
     pri=rand();
     tag=0;
     sz=1;
     mn=val=_val;
    }
};

int Sz(Treap* t) {
 return t?t->sz:0;
}

LL Mn(Treap* t) {
 return t?t->mn:INF;
}

void pull(Treap* t) {
 t->sz = Sz(t->lc) + Sz(t->rc) + 1;
 t->mn = min(min(Mn(t->lc),Mn(t->rc)),t->val);
}

void push(Treap* t) {
// cout<<"t -> Sz = " << Sz(t)<<endl;
 if (t->tag == 0) return;
 if (t->lc) {
     t->lc->val += t->tag;
     t->lc->tag += t->tag;
     t->lc->mn  += t->tag;
    }
 if (t->rc) {
     t->rc->val += t->tag;
     t->rc->tag += t->tag;
     t->rc->mn  += t->tag;
    }
 t->tag=0;
}

Treap* merge(Treap* a,Treap* b) {
 if (!a || !b) return a?a:b;
 else if (a->pri > b->pri) {
     push(a);
     a->rc = merge(a->rc,b);
     pull(a);
     return a;
    }
 else {
     push(b);
     b->lc = merge(a,b->lc);
     pull(b);
     return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
 if (!t) a=b=NULL;
 else if (Sz(t->lc) + 1 <= k) {
     a=t;
     push(a);
     split(t->rc,k-Sz(t->lc)-1,a->rc,b);
     pull(a);
    }
 else {
     b=t;
     push(b);
     split(t->lc,k,a,b->lc);
     pull(b);
    }
}

Treap *root,*unroot;

void pp(Treap* t) {
 if (t==NULL) cout<<"EMPTY";
 if (!t) return;
 if (t->lc)  {
     push(t->lc);
     pp(t->lc);
    }
 cout<<t->val<<' ';
 if (t->rc) {
     push(t->rc);
     pp(t->rc);
    }
}

void insert(int x,LL val) {
 int sz = Sz(root);
 Treap *tl;
 split(root,x,tl,root);
 root = merge(merge(tl,new Treap(val)),root);
 Treap *tr;
 split(unroot,sz-x,unroot,tr);
 unroot = merge(merge(unroot,new Treap(val)),tr);
}

void revolve(int L,int R,LL d) {
 Treap *tl,*tr;
 split(root,R,root,tr);
 split(root,L-1,tl,root);
 d =(d%Sz(root) +  Sz(root) )%Sz(root);
 int sz=Sz(root);
 Treap *m;
 split(root,sz-d,m,root);
 root = merge(merge(tl,root),merge(m,tr));
 Treap *ul,*ur;
 int s=Sz(root);
 split(unroot,s-L+1,unroot,ur);
 split(unroot,s-R,ul,unroot);
 Treap *um;
 split(unroot,d,m,unroot);
 unroot = merge(merge(ul,unroot),merge(m,ur));
}

void add(int L,int R,LL val) {
 Treap *tl,*tr;
 split(root,R,root,tr);
 split(root,L-1,tl,root);
 root->val += val;
 root->tag += val;
 root->mn  += val;
 push(root);
 root = merge(merge(tl,root),tr);
 int sz = Sz(root);
 Treap *ul,*ur;  //sz-R+1 ~ sz-L+1
 split(unroot,sz-L+1,unroot,ur);
 split(unroot,sz-R,ul,unroot);
 unroot->val += val;
 unroot->tag += val;
 unroot->mn  += val;
 push(unroot);
 unroot = merge(merge(ul,unroot),ur);
}

void deleted(int x) {
 int sz = Sz(root);
 Treap *tl,*tr;
 split(root,x,root,tr);
 split(root,x-1,tl,root);
 root = merge(tl,tr);
 x = sz-x+1;
 Treap *ul,*ur;
 split(unroot,x,unroot,ur);
 split(unroot,x-1,ul,unroot);
 unroot = merge(ul,ur);
}

void reverse(int L,int R) {
 Treap *tl,*tr,*ul,*ur;
 int sz = Sz(root);
 split(root,R,root,tr);
 split(root,L-1,tl,root);
    //new : sz-R+1 ~sz-L+1
 split(unroot,sz-L+1,unroot,ur);
 split(unroot,sz-R,ul,unroot);
 Treap* tmp1 = merge(merge(tl,unroot),tr);
 Treap* tmp2 = merge(merge(ul,root),ur);
 unroot = tmp2;
 root   = tmp1;
}

LL Q(int L,int R) {
 Treap *tl,*tr;
 split(root,R,root,tr);
 split(root,L-1,tl,root);
 LL ret=Mn(root);
 root = merge(merge(tl,root),tr);
 return ret;
}

int main () {
 char s[10];
 int n;
 while (scanf("%d",&n) != EOF) {
     root = NULL;
     unroot=NULL;
     for (int x=1;n>=x;x++) {
         LL i;
         scanf("%lld",&i);
         insert(x,i);
        }
     int m;
     scanf("%d",&m);
     while (m--) {
         scanf("%s",s);
         if (!strcmp(s,"ADD")) {
             LL i,j,k;
             scanf("%lld %lld %lld",&i,&j,&k);
             add(i,j,k);
            }
         else if (!strcmp(s,"MIN")) {
             int L,R;
             scanf("%d %d",&L,&R);
             printf("%lld\n",Q(L,R));
            }
         else if (!strcmp(s,"INSERT")) {
             LL i,j;
             scanf("%lld %lld",&i,&j);
             insert(i,j);
            }
         else if (!strcmp(s,"DELETE")) {
             int x;
             scanf("%d",&x);
             deleted(x);
            }
         else if (!strcmp(s,"REVERSE")) {
             int L,R;
             scanf("%d %d",&L,&R);
             reverse(L,R);
            }
         else if (!strcmp(s,"REVOLVE")) {
             LL i,j,k;
             scanf("%lld %lld %lld",&i,&j,&k);
             revolve(i,j,k);
            }
        }
    }
}