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

算法學(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好男人在线观看| 欧美一区二区网站| 国内精品久久久久久| 男女激情久久| 欧美日韩一区二区在线| 性亚洲最疯狂xxxx高清| 久久国产黑丝| 亚洲免费高清视频| 亚洲深爱激情| 伊人久久av导航| 亚洲肉体裸体xxxx137| 欧美性猛交视频| 久久免费的精品国产v∧| 美女脱光内衣内裤视频久久网站| 99精品国产在热久久下载| 正在播放欧美一区| 激情综合色丁香一区二区| 亚洲欧洲在线一区| 国产精品美女在线| 欧美国产欧美亚洲国产日韩mv天天看完整 | 国产精品久久97| 久久久久久久久久久久久女国产乱 | 国产精品一区二区你懂得| 久久人人爽人人爽| 欧美日本在线播放| 久久亚洲精品一区| 欧美性猛交xxxx免费看久久久| 久久另类ts人妖一区二区| 欧美激情一区三区| 久久久久久免费| 欧美三级欧美一级| 欧美激情国产日韩精品一区18| 国产精品va在线播放| 欧美不卡在线视频| 国产精品一国产精品k频道56| 欧美国产日韩一区二区| 国产欧美日韩精品a在线观看| 亚洲国产精品一区制服丝袜| 国产乱码精品一区二区三区av| 亚洲第一免费播放区| 国产一区二区主播在线| 一区二区三区四区五区在线| 亚洲国产精品黑人久久久 | 美国三级日本三级久久99| 欧美亚男人的天堂| 亚洲人成网在线播放| 伊人成人网在线看| 欧美一二区视频| 午夜国产一区| 欧美色大人视频| 亚洲人精品午夜| 亚洲国产精品毛片| 久久人人97超碰精品888| 久久高清国产| 国产精品永久免费在线| 一区二区精品在线| 中日韩美女免费视频网站在线观看| 美日韩精品视频| 免费久久99精品国产自在现线| 国产综合欧美| 久久久五月婷婷| 免费不卡亚洲欧美| 亚洲国产精品久久久久秋霞影院 | 久久一区国产| 欧美国产精品中文字幕| 在线观看的日韩av| 久久午夜精品一区二区| 蜜桃精品一区二区三区| 亚洲电影在线观看| 欧美福利视频在线| 日韩视频在线播放| 亚洲欧美福利一区二区| 国产精品一区一区| 欧美在线视频免费观看| 蜜臀91精品一区二区三区| 亚洲黄色视屏| 欧美激情一区二区三区高清视频 | 亚洲第一福利社区| 日韩写真视频在线观看| 欧美日韩一区综合| 欧美一区91| 欧美成人性生活| 一区二区三区回区在观看免费视频| 欧美日韩亚洲综合在线| 亚洲欧美日韩一区二区在线 | 美女在线一区二区| 亚洲另类在线一区| 国产精品免费小视频| 久久动漫亚洲| 亚洲黄网站黄| 一个色综合av| 国产在线视频欧美| 欧美精品观看| 欧美一级大片在线观看| 欧美激情亚洲精品| 亚洲欧美99| 亚洲国产精品久久91精品| 欧美系列电影免费观看| 久久精品成人一区二区三区| 亚洲精品在线一区二区| 久久国产婷婷国产香蕉| 亚洲精品午夜精品| 国产视频久久| 欧美日本韩国在线| 久久精品国产综合| 亚洲午夜小视频| 亚洲国产精品成人| 久久九九国产| 亚洲一区二区三区在线看| 红桃视频亚洲| 国产精品自拍网站| 欧美日韩免费在线观看| 久久婷婷亚洲| 亚洲欧美精品在线| 一本一道久久综合狠狠老精东影业| 久久久爽爽爽美女图片| 亚洲中无吗在线| 日韩一级欧洲| 亚洲国产91| 好男人免费精品视频| 国产精品一区久久久久| 国产精品s色| 欧美精品在线免费观看| 免费h精品视频在线播放| 久久成人免费| 久久国产精品99久久久久久老狼| 一区二区三区四区五区精品| 91久久嫩草影院一区二区| 美女成人午夜| 蜜桃av噜噜一区| 久热精品视频在线| 久久在线免费观看视频| 欧美中文在线视频| 欧美在线播放视频| 久久超碰97中文字幕| 香蕉久久夜色精品| 欧美一级大片在线观看| 欧美一区二区精品| 久久激情婷婷| 久久久人人人| 欧美成人一区二免费视频软件| 美女啪啪无遮挡免费久久网站| 久久精品国产综合精品| 久久久蜜桃精品| 麻豆精品视频在线观看| 蜜乳av另类精品一区二区| 免费在线播放第一区高清av| 蜜臀久久99精品久久久久久9| 美女精品自拍一二三四| 欧美激情bt| 亚洲精品一区久久久久久| 99亚洲伊人久久精品影院红桃| 在线视频你懂得一区| 亚洲一区二区毛片| 欧美在线播放| 欧美成人精品h版在线观看| 国产日产亚洲精品| 欧美在线免费观看亚洲| 老鸭窝91久久精品色噜噜导演| 免费观看不卡av| 欧美三级电影大全| 国产亚洲成精品久久| 亚洲第一福利视频| 一本久久青青| 亚洲免费视频在线观看| 久久久久欧美| 最新精品在线| 亚洲综合激情| 免费欧美在线视频| 国产精品热久久久久夜色精品三区| 国产亚洲高清视频| 亚洲激情网址| 久久黄色小说| 最近中文字幕mv在线一区二区三区四区 | 在线观看国产一区二区| 99国产精品| 久久久精彩视频| 亚洲精品国产精品久久清纯直播| 亚洲欧美一区二区三区久久| 牛牛影视久久网| 国产精品自拍三区| 99国产一区| 久久亚洲国产成人| 亚洲深夜激情| 欧美黄色一区二区| 伊人夜夜躁av伊人久久| 亚洲欧美视频| 亚洲精品日韩在线观看| 欧美在线免费观看亚洲| 国产精品a久久久久久| 在线精品福利| 久久激情网站| 亚洲一区二区av电影| 欧美a级大片| 一区二区视频免费在线观看| 校园激情久久| 亚洲手机成人高清视频| 欧美日韩国产综合视频在线观看 |