很久以前有且寫過一次splay。。。然后被它要記父親的旋轉囧到。。然后從此就再也沒寫過。。
這幾天剛省選完沒事做，就準備再寫一下。
在sqybi神牛的文章的指導下很快又回憶起了splay的操作。。
于是從頭開始YY一個splay。。?？傮w感覺比treap要難寫。。（Treap性價比真的很高），但要比treap強大許多。。。
感覺上splay完全可以代替線段樹了。。只是常數太大了。。
做了兩道splay的題：
序列終結者 http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1251
CERC2007 sort：http://contest.felk.cvut.cz/07cerc/solved.html
sort這題標程比我多用了一個優化：因為已經排好序的數就沒用了，所以可以從樹里面刪去，從而使整棵樹不斷變小，越來越快。相比我沒用的程序要快了1倍。。 - -！
感覺splay越來越親切了~確實太強大了。。
還有就是我覺得我的splay寫復雜了。。每次寫完都要調各種囧問題。。
求神牛們splay優美漂亮的寫法！。orz

codes:
序列終結者

  1#include <iostream>
  2
  3#define MAXN 50010
  4#define INFINITE 1000000000000000000ll
  5#define MAX(a,b) ((a) > (b) ? (a) : (b))
  6#define ll long long
  7
  8using namespace std;
  9
 10class Node{
 11      public:
 12             int lt, rt, rev, size, fa;
 13             ll v, t, max;
 14             inline void swap(){
 15                  int tmp = lt; lt = rt; rt = tmp;
 16                  rev ^= 1;
 17             }
 18             inline void Add(ll _v){
 19                  v += _v, t += _v, max += _v;
 20             }
 21};
 22Node node[MAXN+1];
 23int cntNode = 0;
 24class SplayTree{
 25      private:
 26              int root;
 27              void Down(int x){
 28                   int lc = node[x].lt, rc = node[x].rt, t;
 29                   if (node[x].rev){
 30                      node[lc].swap(), node[rc].swap();
 31                      node[x].rev = 0;
 32                   }
 33                   if (t = node[x].t){
 34                      node[lc].Add(t), node[rc].Add(t);
 35                      node[x].t = 0;
 36                   }
 37              }
 38              void Renew(int x){
 39                   int lc = node[x].lt, rc = node[x].rt;
 40                   node[x].max = MAX(node[lc].max, node[rc].max);
 41                   node[x].max = MAX(node[x].max, node[x].v);
 42                   node[x].size = node[lc].size + node[rc].size + 1;
 43              }
 44              int Find(int x, int k){
 45                  int lc = node[x].lt;
 46                  if (k == node[lc].size + 1) return x;
 47                  Down(x);
 48                  if (k <= node[lc].size) return Find(lc, k);
 49                  return Find(node[x].rt, k - node[lc].size - 1);
 50              }
 51              void RightRotate(int x){
 52                   int lc = node[x].lt, fa = node[x].fa;
 53                   Down(x); Down(lc);
 54                   node[x].lt = node[lc].rt; node[node[x].lt].fa = x;
 55                   node[lc].rt = x; node[x].fa = lc;
 56                   node[lc].fa = fa;
 57                   if (fa){
 58                      if (x == node[fa].lt)
 59                         node[fa].lt = lc;
 60                      else
 61                          node[fa].rt = lc;
 62                   }
 63                   Renew(x);
 64                   Renew(lc);
 65              }
 66              void LeftRotate(int x){
 67                   int rc = node[x].rt, fa = node[x].fa;
 68                   Down(x); Down(rc);
 69                   node[x].rt = node[rc].lt; node[node[x].rt].fa = x;
 70                   node[rc].lt = x; node[x].fa = rc;
 71                   node[rc].fa = fa;
 72                   if (fa){
 73                      if (x == node[fa].lt)
 74                         node[fa].lt = rc;
 75                      else
 76                          node[fa].rt = rc;
 77                   }
 78                   Renew(x);
 79                   Renew(rc);
 80              }
 81              void Splay(int x, int FA = 0){
 82                   int fa, Fa;
 83                   while ((fa = node[x].fa) != FA){
 84                         if ((Fa = node[fa].fa) == FA){
 85                            if (x == node[fa].lt)
 86                               RightRotate(fa);
 87                            else
 88                                LeftRotate(fa);
 89                         }else{
 90                               if (x == node[fa].lt){
 91                                  if (fa == node[Fa].lt){
 92                                     RightRotate(Fa);
 93                                     RightRotate(fa);
 94                                  }else{
 95                                        RightRotate(fa);
 96                                        LeftRotate(Fa);
 97                                  }
 98                               }else{
 99                                     if (fa == node[Fa].rt){
100                                        LeftRotate(Fa);
101                                        LeftRotate(fa);
102                                     }else{
103                                           LeftRotate(fa);
104                                           RightRotate(Fa);
105                                     }
106                               }
107                         }
108                   }
109                   if (FA == 0)
110                      root = x;
111              }
112              void print(int x){
113                   if (node[x].lt) fprintf(stderr,"%d lt: %d\n",x,node[x].lt), print(node[x].lt);
114                   if (node[x].rt) fprintf(stderr,"%d rt: %d\n",x,node[x].rt), print(node[x].rt);
115              }
116      public:
117             SplayTree():root(0){}
118             void SetRoot(int _root){
119                  root = _root;
120             }
121             int BuildTree(int l, int r, int fa){
122                  if (l>r) return 0;
123                  int x = ++cntNode;
124                  int mid = (l + r) >> 1;
125                  node[x].size = r - l + 1;
126                  node[x].fa = fa;
127                  node[x].lt = BuildTree(l, mid-1, x);
128                  node[x].rt = BuildTree(mid+1,r, x);
129                  return x;
130             }
131             void Reverse(int l, int r){
132                  Splay(l = Find(l-1), 0);
133                  Splay(r = Find(r+1), l);
134                  node[node[r].lt].swap();
135             }
136             void Add(int l, int r, ll v){
137                  Splay(l = Find(l-1), 0);
138                  Splay(r = Find(r+1), l);
139                  node[node[r].lt].Add(v);
140             }
141             ll AskMax(int l, int r){
142                  Splay(l = Find(l-1), 0);
143                  Splay(r = Find(r+1), l);
144                  return node[node[r].lt].max; 
145             }
146             int Find(int k){
147                  return Find(root, k);
148             }
149             void print(){
150                  print(root);
151                  for (int i = 1; i<=cntNode; i++)
152                      fprintf(stderr, "%d ", node[i].max);
153                  fprintf(stderr, "\n");
154             }
155}T;
156#define BUFSIZE 100000*100
157char buf[BUFSIZE+1], *pt = buf;
158ll Sign;
159//void scan_int(int &t)
160#define scan_int(t) \
161{  \
162   t = 0;  \
163   while ((!((*pt) >= '0' && (*pt) <= '9')) && (*pt)!='-') pt++;  \
164   if ((*(pt)) == '-') Sign = -1, pt++; else Sign = 1;  \
165   while (((*pt) >= '0' && (*pt) <= '9')) t = t * 10ll + (*(pt++)) - '0';  \
166   t *= Sign;  \
167}
168
169/**//*
170void scan_int(ll &t)
171{ 
172   t = 0; 
173   while ((!((*pt) >= '0' && (*pt) <= '9')) && (*pt)!='-') pt++; 
174   if ((*(pt)) == '-') Sign = -1, pt++; else Sign = 1; 
175   while (((*pt) >= '0' && (*pt) <= '9')) t = t * 10ll + (*(pt++)) - '0'; 
176   t *= Sign; 
177}
178*/
179int main()
180{
181    int n,m;
182    scanf("%d%d",&n,&m);
183    T.SetRoot(T.BuildTree(0, n+1, 0));
184#ifdef DEBUG
185    T.print();
186#endif
187    node[0].max = -INFINITE;
188    int cmd, l, r;
189    ll v;
190    fread(buf, 1, BUFSIZE, stdin);
191    while (m--){
192          //scanf("%d%d%d",&cmd,&l,&r);
193          scan_int(cmd); scan_int(l); scan_int(r);
194          l++, r++;
195          if (cmd == 1){
196             //scanf("%I64d",&v);
197             scan_int(v);
198             T.Add(l, r, v);
199          }else if (cmd == 2)
200                T.Reverse(l, r);
201          else if (cmd == 3)
202               printf("%I64d\n", T.AskMax(l, r));
203#ifdef DEBUG
204          T.print();
205#endif
206    }
207    return 0;
208}
209
210

  1#include <iostream>
  2#define MAXN 100010
  3#define INFINITE 1000000000
  4#define MIN(a,b) ((a) < (b) ? (a) : (b))
  5
  6using namespace std;
  7
  8class Stuff{
  9      public:
 10             int id,v;
 11};
 12class SplayNode{
 13      public:
 14             int lt, rt, fa, size, v, rev, min;
 15             void Reverse(){
 16                  rev ^= 1;
 17                  int tmp = lt; lt = rt; rt = tmp;
 18             }
 19};
 20SplayNode node[MAXN+1];
 21int cntNode = 0;
 22class SplayTree{
 23      private:
 24              int root;
 25              void Renew(int x){
 26                   int lc = node[x].lt, rc = node[x].rt;
 27                   node[x].min = MIN(node[lc].min, node[rc].min);
 28                   node[x].min = MIN(node[x].min, node[x].v);
 29                   node[x].size = node[lc].size + node[rc].size + 1;
 30              }
 31              void Down(int x){
 32                   if (node[x].rev){
 33                      node[node[x].lt].Reverse(); node[node[x].rt].Reverse();
 34                      node[x].rev = 0;
 35                   }
 36              }
 37              int FindMinPos(int x, int v){
 38                  if (node[x].v == v) return node[node[x].lt].size + 1;
 39                  Down(x);
 40                  if (node[node[x].lt].min == v) return FindMinPos(node[x].lt, v);
 41                  return node[node[x].lt].size + 1 + FindMinPos(node[x].rt, v);
 42              }
 43              int FindKthID(int x, int k){
 44                  if (k == node[node[x].lt].size + 1) return x;
 45                  Down(x);
 46                  if (k <= node[node[x].lt].size) return FindKthID(node[x].lt, k);
 47                  return FindKthID(node[x].rt, k - node[node[x].lt].size - 1);
 48              }
 49              void RightRotate(int x){
 50                   int lc = node[x].lt, fa = node[x].fa;
 51                   Down(x); Down(lc);
 52                   node[x].lt = node[lc].rt; node[node[x].lt].fa = x;
 53                   node[lc].rt = x; node[x].fa = lc;
 54                   node[lc].fa = fa;
 55                   if (fa){
 56                      if (x == node[fa].lt) node[fa].lt = lc;
 57                      else node[fa].rt = lc;
 58                   }
 59                   Renew(x); Renew(lc);
 60              }
 61              void LeftRotate(int x){
 62                   int rc = node[x].rt, fa = node[x].fa;
 63                   Down(x); Down(rc);
 64                   node[x].rt = node[rc].lt; node[node[x].rt].fa = x;
 65                   node[rc].lt = x; node[x].fa = rc;
 66                   node[rc].fa = fa;
 67                   if (fa){
 68                      if (x == node[fa].lt) node[fa].lt = rc;
 69                      else node[fa].rt = rc;
 70                   }
 71                   Renew(x); Renew(rc);
 72              }
 73              void Splay(int x, int FA = 0){
 74                   int fa, Fa;
 75                   while ((fa = node[x].fa) != FA){
 76                         if ((Fa = node[fa].fa) == FA){
 77                            if (x == node[fa].lt)
 78                               RightRotate(fa);
 79                            else
 80                                LeftRotate(fa);
 81                         }else{
 82                               if (x == node[fa].lt){
 83                                  if (fa == node[Fa].lt)
 84                                     RightRotate(Fa), RightRotate(fa);
 85                                  else
 86                                      RightRotate(fa), LeftRotate(Fa);
 87                               }else{
 88                                     if (fa == node[Fa].rt)
 89                                        LeftRotate(Fa), LeftRotate(fa);
 90                                     else
 91                                         LeftRotate(fa), RightRotate(Fa);
 92                               }
 93                         }
 94                   }
 95                   if (FA == 0) root = x;
 96              }
 97              void Print(int x){
 98                   int t;
 99                   if (t = node[x].lt) fprintf(stderr, "%d lt: %d\n", x, t), Print(t);
100                   if (t = node[x].rt) fprintf(stderr, "%d rt: %d\n", x, t), Print(t);
101              }
102      public:
103             void Reset(){
104                  node[0].min = INFINITE;
105                  cntNode = 0;
106             }
107             void SetRoot(int _root){
108                  root = _root;
109             }
110             int FindKthID(int k){
111                 return FindKthID(root, k);
112             }
113             int BuildTree(int l, int r, int *a, int fa = 0){
114                 if (l > r) return 0;
115                 int x = ++cntNode;
116                 int mid = (l + r) >> 1;
117                 node[x].fa = fa, node[x].v = a[mid], node[x].size = 1;
118                 node[x].rev = 0;
119                 node[x].lt = BuildTree(l, mid - 1, a, x);
120                 node[x].rt = BuildTree(mid + 1, r, a, x);
121                 Renew(x);
122                 return x;
123                 }
124             int AskMinPos(int l, int r){
125                 l = FindKthID(l - 1);
126                 Splay(l, 0);
127                 r = FindKthID(r + 1);
128                 Splay(r, l);
129                 return node[node[l].lt].size + 1 + FindMinPos(node[r].lt, node[node[r].lt].min);
130             }
131             void Reverse(int l, int r){
132                  if (l == r) return;
133                  Splay(l = FindKthID(l - 1), 0);
134                  Splay(r = FindKthID(r + 1), l);
135                  node[node[r].lt].Reverse();
136             }
137             int Print(){
138                  Print(root);
139                  fprintf(stderr, "\n");
140                  return 0;
141             }
142};
143
144Stuff a[MAXN+1];
145SplayTree T;
146int b[MAXN+1];
147int n;
148bool Init(){
149     scanf("%d",&n);
150     if (!n)
151        return false;
152     for (int i = 1; i<=n; i++)
153         scanf("%d",&a[i].v), a[i].id = i;
154}
155
156
157int cmpStuff(const void *a, const void *b){
158    Stuff _a = (*(Stuff *)a), _b = (*(Stuff *)b);
159    if (_a.v != _b.v) return _a.v - _b.v;
160    return _a.id - _b.id;
161}
162
163//#define DEBUG
164void Solve(){
165     // Discretization
166     a[0].v = -INFINITE;
167     a[n+1].v = INFINITE, a[n+1].id = n+1;
168     qsort(a, n+2, sizeof(a[0]), cmpStuff);
169     for (int i = 0; i<=n+1; i++)
170         b[a[i].id] = i;
171     
172     // Build Tree
173     // Make the initial tree balanced
174     T.Reset();
175     T.SetRoot(T.BuildTree(0, n+1, b));
176#ifdef DEBUG
177     T.Print();
178#endif
179     // Work
180     int p;
181     for (int i = 1; i<=n; i++){
182         printf("%d ", (p = T.AskMinPos(i+1, n+1)) - 1);
183#ifdef DEBUG
184         fprintf(stderr, "%d ", p - 1);
185#endif
186         T.Reverse(i+1, p);
187     }
188     printf("\n");
189#ifdef DEBUG
190     fprintf(stderr, "\n");
191#endif
192}
193
194int main(){
195    freopen("s.in","r",stdin);
196    freopen("s.out","w",stdout);
197    while (Init())
198           Solve();
199    return 0;
200}
201