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

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 閱讀(977) 評論(2)  編輯 收藏 引用
評論:

只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


 
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>
            
欧美午夜在线视频|
免费亚洲一区二区|
亚洲一区二区高清视频|
欧美日韩成人一区二区|
夜夜嗨网站十八久久|
午夜精品福利在线观看|
激情综合网激情|
欧美另类在线播放|
午夜精品视频|
亚洲成色777777在线观看影院|
亚洲国产综合91精品麻豆|
老司机一区二区三区|
aaa亚洲精品一二三区|
久久手机精品视频|
日韩一级精品|
国产在线视频欧美|
欧美日韩大片|
久久久久中文|
中文一区二区|
欧美韩国日本一区|
欧美一区日本一区韩国一区|
亚洲日本成人网|
国产午夜精品麻豆|
欧美日韩一区在线观看视频|
久久久蜜桃精品|
亚洲永久精品大片|
亚洲精品1区2区|
久久最新视频|
午夜在线电影亚洲一区|
亚洲精品国产精品国产自|
国产人久久人人人人爽|
欧美精品自拍|
免费成人高清|
久久精品视频在线看|
亚洲一级片在线观看|
亚洲国产天堂久久综合网|
久久久久久电影|
午夜精品久久久久久久99热浪潮|
亚洲精品国产精品国自产观看|
国产视频欧美|
国产精品日韩久久久久|
欧美久久综合|
免费日韩av电影|
久久久亚洲国产美女国产盗摄|
午夜国产精品影院在线观看|
99视频精品|
亚洲精品乱码久久久久久黑人|
欧美va天堂在线|
久久亚洲国产精品日日av夜夜|
午夜精品美女自拍福到在线|
99精品欧美一区二区三区综合在线|
在线观看国产精品淫|
国产资源精品在线观看|
国产欧美一区二区精品婷婷|
日韩一级精品|
亚洲国产精品99久久久久久久久|
久久精品中文字幕免费mv|
日韩视频永久免费观看|
国产日韩欧美综合在线|
欧美日韩八区|
欧美日本中文|
欧美激情一区二区三区全黄|
欧美91福利在线观看|
国产精品99久久久久久宅男|
在线视频亚洲|
久久九九有精品国产23|
欧美精品观看|
国产欧美激情|
最新国产精品拍自在线播放|
亚洲午夜女主播在线直播|
久久久久久久999|
亚洲欧洲精品成人久久奇米网|
亚洲一区二区久久|
久久在线免费观看视频|
欧美日韩美女一区二区|
国产午夜精品一区理论片飘花|
亚洲国产老妈|
午夜免费电影一区在线观看|
欧美freesex交免费视频|
日韩一区二区精品在线观看|
欧美亚洲一级片|
欧美激情精品久久久久久免费印度|
国产精品麻豆成人av电影艾秋|
在线不卡a资源高清|
亚洲在线观看免费|
免费欧美日韩国产三级电影|
亚洲午夜国产一区99re久久|
久热精品在线|
亚洲久久成人|
久久精品一区二区|
欧美色中文字幕|
在线观看日韩av|
亚洲欧美日韩另类|
亚洲电影在线播放|
亚洲欧美大片|
欧美日韩第一区|
亚洲电影免费观看高清完整版在线|
亚洲欧美激情四射在线日|
欧美黄色一区二区|
欧美一区二区三区四区在线|
欧美日韩亚洲另类|
亚洲激情视频网|
久久免费国产精品|
亚洲午夜视频在线观看|
欧美岛国在线观看|
精品不卡一区|
欧美在线亚洲|
中日韩美女免费视频网址在线观看|
欧美aa国产视频|
精品999成人|
久久精品人人做人人综合
|
亚洲国产精品第一区二区三区|
亚洲欧美日韩中文视频|
亚洲精品视频在线|
玖玖综合伊人|
在线精品福利|
久久中文字幕导航|
欧美亚洲在线|
国产美女精品视频免费观看|
亚洲一区二区三区中文字幕在线|
亚洲国产精品福利|
久热精品在线|
在线免费观看欧美|
久久夜色精品亚洲噜噜国产mv|
亚洲欧美日韩国产|
国产精品亚洲精品|
亚洲女同性videos|
中国成人在线视频|
国产精品久久久久久久免费软件|
亚洲午夜久久久|
一区二区三区你懂的|
欧美午夜精品久久久久久超碰|
一区二区三区精品在线|
在线观看国产日韩|
美国成人直播|
久久久中精品2020中文|
娇妻被交换粗又大又硬视频欧美|
久久午夜电影网|
久久免费少妇高潮久久精品99|
一区在线免费观看|
亚洲婷婷国产精品电影人久久|
欧美激情中文字幕一区二区|
免费国产自线拍一欧美视频|
亚洲国产天堂久久综合|
欧美激情久久久久|
欧美国产精品专区|
一本久久a久久免费精品不卡|
亚洲毛片av|
国产精品久久久久久久午夜|
欧美一级黄色录像|
午夜精品视频一区|
狠狠干成人综合网|
欧美国产精品劲爆|
欧美精品亚洲精品|
亚洲永久在线|
欧美一区二区视频97|
久久不见久久见免费视频1|
国产三级欧美三级日产三级99|
久久久99国产精品免费|
久久久久久久久久久久久9999|
亚洲国产精品va在线观看黑人|
亚洲国产天堂久久国产91|
欧美性开放视频|
久久高清一区|
久久综合狠狠综合久久综合88
|
亚洲欧洲中文日韩久久av乱码|
亚洲国产免费|
国产精品久久久久久五月尺|
久久精品亚洲精品|
美女露胸一区二区三区|
在线视频精品一区|
午夜一区在线|
最新国产の精品合集bt伙计|
亚洲一区二区成人在线观看|
狠狠色香婷婷久久亚洲精品|
亚洲国产高清一区|
国产精品久久久一区麻豆最新章节|
久久九九精品99国产精品|
欧美成年人视频网站欧美|
亚洲欧美另类在线观看|
久久久久久一区|
中文成人激情娱乐网|
欧美专区在线观看一区|
亚洲巨乳在线|
欧美亚洲一级|
一区二区三区四区国产精品|
欧美在线啊v|
99视频精品在线|
久久成人精品|
中文日韩在线视频|
久久免费精品日本久久中文字幕|
亚洲性视频网址|
久久久久久网|
亚洲——在线|
玖玖玖免费嫩草在线影院一区|
亚洲综合第一页|
久久综合久色欧美综合狠狠|
午夜精品久久久久久99热|
嫩草伊人久久精品少妇av杨幂|
亚洲免费小视频|