題目描述：
給一個(gè)長(zhǎng)度為N(N<10,000)的數(shù)列，每次選取值最小的元素并翻轉(zhuǎn)前面的數(shù)列，然后刪除這個(gè)元素。請(qǐng)?jiān)诿看尾僮髦拜敵鲞@個(gè)最小元素的位置。
吐槽：
1. 很好的splay熱身題，強(qiáng)勢(shì)推薦....
2. 自底向上的維護(hù)對(duì)于懶惰標(biāo)記的向下傳遞好像很無(wú)力？ NO！ 寫過(guò)zkw版線段樹么.... 看我
之前寫過(guò)的一篇題解吧！ 自底向上同樣可以傳遞懶惰標(biāo)記。
算法分析：
這里的splay應(yīng)用是... 放棄了元素之間的優(yōu)先級(jí)，完全模擬一個(gè)數(shù)組(像笛卡爾樹那樣)
要解決一些問(wèn)題：
1. 如何查找元素最小的元素？ 記錄最小值？ NO! 數(shù)列的數(shù)組下標(biāo)和splay的下標(biāo)是一樣的！！！！
2. 如何翻轉(zhuǎn)一個(gè)區(qū)間？ 先把這個(gè)區(qū)間“抽”出來(lái)，然后在這個(gè)區(qū)間的代表節(jié)點(diǎn)上加一個(gè)標(biāo)記，傳遞標(biāo)記的時(shí)候就旋轉(zhuǎn)左右子樹。
3. 如何刪除節(jié)點(diǎn)？ 找到節(jié)點(diǎn)的前驅(qū)與后繼，然后通過(guò)splay前驅(qū)與后繼把這個(gè)節(jié)點(diǎn)“抽”出來(lái)。
4. 如何在向上splay的時(shí)候傳遞懶惰標(biāo)記？ 看我之前一篇題解吧！ 在splay之前更新所有的父親節(jié)點(diǎn)！
HDU代碼長(zhǎng)度第三 ~~ 繼續(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
西月弦 閱讀(1177)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告