题目描述:
给一个长度为N(N<10,000)的数列,每次选取值最小的元素并翻转前面的数列,然后删除这个元素。请在每次操作之前输出这个最小元素的位置。
吐槽:
1. 很好的splay热身题,强势推荐....
2. 自底向上的维护对于懒惰标记的向下传递好像很无力? NO! 写过zkw版线段树么.... 看我
之前写过的一篇题解吧! 自底向上同样可以传递懒惰标记。
算法分析:
这里的splay应用是... 放弃了元素之间的优先级,完全模拟一个数组(像笛卡尔树那样)
要解决一些问题:
1. 如何查找元素最小的元素? 记录最小值? NO! 数列的数组下标和splay的下标是一样的!!!!
2. 如何翻转一个区间? 先把这个区间“抽”出来,然后在这个区间的代表节点上加一个标记,传递标记的时候就旋转左右子树。
3. 如何删除节点? 找到节点的前驱与后继,然后通过splay前驱与后继把这个节点“抽”出来。
4. 如何在向上splay的时候传递懒惰标记? 看我之前一篇题解吧! 在splay之前更新所有的父亲节点!
HDU代码长度第三 ~~ 继续figo的传统
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
西月弦 阅读(1152)
评论(0) 编辑 收藏 引用 所属分类:
解题报告