青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Tim's Programming Space  
Tim's Programming Space
日歷
<2010年4月>
日一二三四五六
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678
統計
  • 隨筆 - 20
  • 文章 - 1
  • 評論 - 40
  • 引用 - 0

導航

常用鏈接

留言簿(3)

隨筆檔案

文章檔案

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

 

很久以前有且寫過一次splay。。。然后被它要記父親的旋轉囧到。。然后從此就再也沒寫過。。
這幾天剛省選完沒事做，就準備再寫一下。
在sqybi神牛的文章的指導下很快又回憶起了splay的操作。。
于是從頭開始YY一個splay。。。總體感覺比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


sort：
  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
posted on 2010-04-09 14:43 TimTopCoder 閱讀(973) 評論(2)  編輯 收藏 引用
評論:
 
Copyright © TimTopCoder Powered by: 博客園 模板提供：滬江博客
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
欧美高清视频在线观看|
老司机成人网|
欧美理论电影在线播放|
日韩午夜av|
久久婷婷久久一区二区三区|
国产喷白浆一区二区三区|
香蕉久久一区二区不卡无毒影院|
99av国产精品欲麻豆|
欧美日韩国产小视频在线观看|
亚洲精品日日夜夜|
亚洲免费观看在线视频|
国产精品―色哟哟|
久久亚洲一区二区|
欧美电影免费观看网站|
日韩视频永久免费|
一区二区三区免费看|
国产精品视频久久久|
免费短视频成人日韩|
欧美精品在线观看播放|
亚洲专区一区|
久久一区二区三区超碰国产精品|
亚洲精品久久久久久久久久久久久
|
午夜一级在线看亚洲|
国产精品久久久久高潮|
可以免费看不卡的av网站|
欧美久久视频|
久久精品91久久久久久再现|
欧美激情第10页|
久久综合九色综合欧美狠狠|
国产精品乱子久久久久|
日韩视频在线一区二区三区|
雨宫琴音一区二区在线|
中日韩男男gay无套|
亚洲三级毛片|
免费观看亚洲视频大全|
国产精品乱码一区二三区小蝌蚪|
亚洲激情女人|
亚洲第一精品夜夜躁人人躁|
欧美中文字幕在线观看|
欧美一区二区三区视频|
欧美日韩一区综合|
亚洲三级影院|
亚洲理论在线观看|
欧美国产综合视频|
亚洲黄色大片|
亚洲美女在线观看|
欧美精品久久久久久|
亚洲日本电影在线|
亚洲美女视频网|
国产精品女主播|
中文欧美日韩|
久久久999精品|
伊人久久婷婷|
欧美日韩三级在线|
性欧美video另类hd性玩具|
国产精品美女xx|
亚洲欧美日本视频在线观看|
久久久久久综合|
日韩天堂av|
国产午夜精品理论片a级探花|
久久精品一区二区国产|
免费成年人欧美视频|
99国内精品|
一区二区亚洲精品国产|
国产精品magnet|
六十路精品视频|
久久爱www.|
在线一区亚洲|
亚洲美女免费视频|
麻豆久久久9性大片|
一本色道久久综合狠狠躁篇怎么玩
|
午夜一区二区三区不卡视频|
亚洲国产精品久久久久婷婷老年|
欧美日韩一区二区三区免费看|
久久久久久婷|
亚洲午夜视频|
亚洲毛片一区二区|
美女视频网站黄色亚洲|
久久亚洲美女|
亚洲欧美一区二区视频|
亚洲视频网在线直播|
亚洲精品永久免费精品|
亚洲国产成人久久综合|
一区二区三区在线视频观看|
狠色狠色综合久久|
亚洲高清视频一区|
亚洲免费观看高清完整版在线观看熊|
依依成人综合视频|
亚洲人精品午夜|
亚洲午夜电影在线观看|
午夜久久久久久|
久久亚洲综合网|
亚洲国产日韩在线一区模特|
亚洲人被黑人高潮完整版|
亚洲另类自拍|
久久精品亚洲乱码伦伦中文|
媚黑女一区二区|
国产精品美女主播在线观看纯欲|
国产麻豆精品视频|
亚洲国产欧美一区二区三区同亚洲
|
欧美视频在线观看一区|
国产亚洲精品aa午夜观看|
亚洲人午夜精品免费|
欧美在线看片|
亚洲精品免费一二三区|
亚洲欧美激情一区二区|
欧美在线免费视屏|
亚洲精品国产精品国自产观看浪潮|
一区二区日韩欧美|
你懂的视频一区二区|
国产日韩欧美电影在线观看|
日韩视频―中文字幕|
欧美成人一区二区三区在线观看|
一本色道久久综合精品竹菊
|
中文一区二区|
亚洲国产网站|
久久视频在线免费观看|
国产精品一卡二卡|
亚洲制服欧美中文字幕中文字幕|
亚洲高清精品中出|
欧美成人国产va精品日本一级|
国产精品少妇自拍|
欧美一区二区三区免费大片|
亚洲深夜福利在线|
欧美精品一区三区在线观看|
亚洲国产日韩综合一区|
欧美风情在线|
欧美精品www|
亚洲欧美精品在线|
午夜精品一区二区三区在线|
国产精品免费观看视频|
午夜伦欧美伦电影理论片|
亚洲欧美中文另类|
在线欧美福利|
亚洲精品国精品久久99热|
欧美精品18videos性欧美|
日韩视频国产视频|
欧美一区二区黄色|
影音先锋久久资源网|
亚洲精品影院在线观看|
国产精品永久免费观看|
欧美成人一区二免费视频软件|
欧美黑人一区二区三区|
亚洲女与黑人做爰|
女女同性女同一区二区三区91|
一区二区三区不卡视频在线观看|
亚洲欧美大片|
亚洲色在线视频|
免费在线亚洲|
国产精品亚洲不卡a|
国产精品影视天天线|
最新国产成人av网站网址麻豆|
国产日韩欧美日韩|
99精品国产99久久久久久福利|
国产综合久久久久久|
亚洲日本视频|
亚洲三级视频|
久久亚洲不卡|
久久国产99|
国产色爱av资源综合区|
夜夜夜久久久|
一区二区三区国产精华|
老司机亚洲精品|
国产欧美亚洲日本|
亚洲精品视频二区|
一本久久综合|
麻豆精品视频在线|
欧美中在线观看|
国产日韩欧美制服另类|
日韩亚洲欧美中文三级|
亚洲欧美日本国产有色|
国产视频精品va久久久久久|
亚洲综合大片69999|
欧美中文在线观看国产|
国际精品欧美精品|
久久精品国产久精国产思思|
国产在线播放一区二区三区|
久久精品夜色噜噜亚洲a∨|
欧美成人精品|
亚洲视频免费|
国产午夜精品美女视频明星a级|
中日韩在线视频|
欧美/亚洲一区|
一区二区三区视频在线看|
欧美丝袜一区二区三区|
欧美一区二区三区精品电影|
男人的天堂亚洲在线|
日韩视频一区二区|
国产欧美一区二区精品秋霞影院|
亚洲欧美在线一区|
国产欧美日韩在线观看|
午夜国产精品影院在线观看|
欧美国产欧美亚州国产日韩mv天天看完整
|
国产精品一区一区三区|
久久综合999|
91久久久在线|
国产丝袜一区二区|
欧美日韩国产综合久久|
久久精品国产第一区二区三区最新章节|
亚洲电影自拍|