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

算法學(xué)社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

題目描述:

   給一個(gè)長度為N(N<10,000)的數(shù)列,每次選取值最小的元素并翻轉(zhuǎn)前面的數(shù)列,然后刪除這個(gè)元素。請(qǐng)?jiān)诿看尾僮髦拜敵鲞@個(gè)最小元素的位置。

吐槽:

    1. 很好的splay熱身題,強(qiáng)勢(shì)推薦....
    2. 自底向上的維護(hù)對(duì)于懶惰標(biāo)記的向下傳遞好像很無力? NO! 寫過zkw版線段樹么.... 看我之前寫過的一篇題解吧! 自底向上同樣可以傳遞懶惰標(biāo)記。

算法分析:

    這里的splay應(yīng)用是... 放棄了元素之間的優(yōu)先級(jí),完全模擬一個(gè)數(shù)組(像笛卡爾樹那樣)
    要解決一些問題:
        1. 如何查找元素最小的元素? 記錄最小值? NO! 數(shù)列的數(shù)組下標(biāo)和splay的下標(biāo)是一樣的!!!!
        2. 如何翻轉(zhuǎn)一個(gè)區(qū)間? 先把這個(gè)區(qū)間“抽”出來,然后在這個(gè)區(qū)間的代表節(jié)點(diǎn)上加一個(gè)標(biāo)記,傳遞標(biāo)記的時(shí)候就旋轉(zhuǎn)左右子樹。
        3. 如何刪除節(jié)點(diǎn)? 找到節(jié)點(diǎn)的前驅(qū)與后繼,然后通過splay前驅(qū)與后繼把這個(gè)節(jié)點(diǎn)“抽”出來。
        4. 如何在向上splay的時(shí)候傳遞懶惰標(biāo)記? 看我之前一篇題解吧! 在splay之前更新所有的父親節(jié)點(diǎn)!
    HDU代碼長度第三 ~~ 繼續(xù)figo的傳統(tǒng)
 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<cassert>
 4 using namespace std;
 5 const int N = 100005;
 6 int n,splsize;
 7 struct node{
 8     int flag,sz,ch[2],p;
 9 } tree[N];
10 struct sample{
11     int id,v;
12     bool operator < (sample A) const{
13         return A.v == v ? id < A.id : v < A.v;
14     }
15 }num[N];
16 // splay
17 inline void upt(int x){
18     tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz+1;
19 }
20 inline void setchd(int y,int x,int p){
21     tree[y].ch[p] = x; tree[x].p = y;
22 }
23 void rot(int x){
24     int y = tree[x].p;
25     int chd = tree[y].ch[1] == x;
26     setchd(tree[y].p,x,tree[tree[y].p].ch[1] == y);
27     setchd(y,tree[x].ch[chd^1],chd);
28     setchd(x,y,chd^1);
29     upt(y);  upt(x);
30 }
31 void pushup(int x){
32     if(tree[x].flag) {
33         tree[x].flag=0;
34         swap(tree[x].ch[0],tree[x].ch[1]);
35         tree[tree[x].ch[0]].flag ^= 1;
36         tree[tree[x].ch[1]].flag ^= 1;
37     }
38 }
39 void dfs(int x){
40     if(!x) return ;
41     dfs(tree[x].p);
42     pushup(x);
43 }
44 void splay(int x,int rt){
45     dfs(x);
46     while(tree[x].p!=rt){
47         int y = tree[x].p;
48         int flag = tree[y].ch[1] == x;
49         if(tree[tree[x].p].p !=rt && flag == (tree[tree[y].p].ch[1] == y)) rot(y);
50         rot(x);
51     }
52 }
53 // function
54 void ins(int x){
55     setchd(x-1,x,1);
56     tree[x].ch[0] = tree[x].ch[1] = tree[x].flag= 0;
57     splay(x,0);
58 }
59 int cal(int x){
60     splay(x,0);
61     int ans = tree[tree[x].ch[0]].sz +1;
62     tree[tree[x].ch[0]].flag ^=1;
63     int u = tree[x].ch[0];
64     int v = tree[x].ch[1];
65     if(u==0) setchd(0,v,1);
66     else if(v==0) setchd(0,u,1);
67     else {
68         pushup(u); pushup(v);
69         while(tree[u].ch[1]){ u = tree[u].ch[1]; pushup(u);}
70         while(tree[v].ch[0]){ v = tree[v].ch[0]; pushup(v);}
71         splay(u,0);     splay(v,u); 
72         assert(tree[v].ch[0] == x);
73         tree[v].ch[0] = 0;
74     }
75     return ans;
76 }
77 // main
78 int main(){
79     tree[0].ch[0] = tree[0].ch[1] = tree[0].p = 0;
80     while(~scanf("%d",&n) && n){
81         for(int i=0; i<n; i++){
82             scanf("%d",&num[i].v);
83             ins(i+1);
84             num[i].id = i;
85         }
86         sort(num,num+n);
87         for(int i=0; i<n; i++){
88             int pos = num[i].id + 1;
89             int ans = cal(pos) + i;
90             if(i) printf(" ");
91             printf("%d",ans);
92         }
93         puts("");
94     }
95 }
96 
posted on 2012-05-10 20:54 西月弦 閱讀(1166) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 解題報(bào)告
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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网站| 亚洲午夜精品久久久久久app| 国产日韩欧美一区二区三区在线观看 | 极品尤物av久久免费看| 欧美电影免费观看大全| 欧美日韩免费看| 久久久久久久成人| 欧美激情一区二区三区在线视频观看| 在线中文字幕一区| 久久精品中文字幕一区二区三区| 亚洲日本视频| 亚洲免费视频中文字幕| 在线观看欧美日韩| 99国内精品久久| 精品成人一区二区三区四区| 亚洲精品影视| 精品av久久久久电影| 99re6这里只有精品视频在线观看| 国产乱码精品| 91久久在线观看| 国语精品一区| 亚洲精品无人区| 亚洲私人影院在线观看| 亚洲激情不卡| 先锋影音国产精品| 亚洲性色视频| 久久亚洲精品视频| 欧美在线91| 欧美人妖在线观看| 欧美成人蜜桃| 国产亚洲成人一区| 亚洲天堂av高清| 亚洲黄色av| 久久久久久亚洲精品中文字幕 | 国产色综合网| 亚洲视频 欧洲视频| 亚洲日本精品国产第一区| 久久高清一区| 欧美中文字幕在线观看| 欧美日韩一二三四五区| 亚洲国产成人高清精品| 伊人久久综合| 久久精品动漫| 久久九九精品99国产精品| 国产精品久久国产精品99gif| 亚洲国产成人高清精品| 亚洲欧洲精品一区二区三区不卡| 欧美永久精品| 久久久九九九九| 国产精品网站视频| 亚洲淫片在线视频| 香蕉久久夜色精品国产| 欧美网站在线观看| 在线亚洲美日韩| 一区二区三区成人| 欧美三级在线视频| 亚洲最新色图| 亚洲欧美一区二区激情| 国产精品夜夜夜一区二区三区尤| 亚洲性视频网址| 小辣椒精品导航| 国产精一区二区三区| 亚洲女爱视频在线| 久久视频这里只有精品| 亚洲第一天堂av| 欧美成人午夜激情| 一本色道久久88精品综合| 亚洲一级在线观看| 国产欧美日韩中文字幕在线| 欧美一级久久久久久久大片| 免费观看亚洲视频大全| 亚洲欧洲一区二区天堂久久| 欧美精品一区在线播放| 亚洲手机视频| 久久这里有精品视频| 亚洲国产精品123| 欧美日韩一区二区在线| 亚洲欧美国产三级| 免费日韩av| 亚洲一区二区三区在线观看视频| 国产美女精品免费电影| 久久综合电影| 亚洲日韩第九十九页| 欧美亚洲动漫精品| 久久精品30| 日韩视频免费在线观看| 久久久精品一区二区三区| 亚洲精品久久在线| 国产日韩欧美精品| 欧美成人小视频| 亚洲欧美日韩在线一区| 亚洲大胆女人| 欧美中文字幕视频| 99精品免费视频| 国产在线精品一区二区中文| 欧美精品 日韩| 欧美在线视屏| 亚洲精品一二区| 久久综合给合| 亚洲尤物在线视频观看| 亚洲国产成人精品久久| 国产免费观看久久黄| 欧美国产精品一区| 久久久久一区| 亚洲女同性videos| 亚洲精品在线一区二区| 久热精品视频在线| 香蕉国产精品偷在线观看不卡| 亚洲欧洲日本专区| 韩国一区二区三区美女美女秀| 欧美视频一区二区三区| 欧美成人69| 久久一区二区三区四区| 午夜精品一区二区三区在线视| 亚洲乱码国产乱码精品精| 欧美成人精品不卡视频在线观看| 久久国产日韩| 欧美在线999| 亚洲欧美日韩在线播放| 宅男在线国产精品| 99在线视频精品| 91久久在线观看| 亚洲国产三级| 亚洲电影一级黄| 在线观看91精品国产入口| 韩国一区电影| 又紧又大又爽精品一区二区| 国产日韩精品视频一区二区三区| 国产精品v片在线观看不卡| 欧美精品久久99| 欧美精品二区| 欧美剧在线观看| 欧美日韩精品欧美日韩精品 | 99国产一区| 亚洲精品女人| 99re国产精品| 一区二区黄色| 亚洲伊人一本大道中文字幕| 亚洲免费网址| 久久国产色av| 美女露胸一区二区三区| 欧美刺激午夜性久久久久久久| 欧美不卡在线视频| 最新日韩在线视频| 一本色道久久99精品综合| 亚洲手机在线| 久久精品三级| 欧美精品91| 国产精品日韩专区| 黑丝一区二区| 亚洲美女中文字幕| 亚洲制服少妇| 久久偷窥视频| 亚洲欧洲一区二区三区久久| 一本久久精品一区二区| 欧美一区二区三区的| 久久视频一区| 欧美日韩在线精品| 国产一区二区黄色| 亚洲六月丁香色婷婷综合久久| 亚洲一区二区免费视频| 久久精品在线免费观看| 亚洲国产精品精华液2区45| 一本一本久久a久久精品牛牛影视| 亚洲主播在线| 免费视频最近日韩| 国产欧美精品| 亚洲国产日韩欧美| 欧美亚洲网站| 亚洲福利在线观看| 午夜精品理论片| 欧美激情一区三区| 韩国女主播一区| 亚洲午夜精品网| 欧美99在线视频观看| 亚洲综合三区| 欧美国产亚洲另类动漫| 国产亚洲午夜| 亚洲图片在线观看| 欧美国产免费| 欧美伊人影院| 国产精品日韩在线播放| 99精品视频一区二区三区| 久久天堂成人| 亚洲图中文字幕|