題目簡介:
用一個數據結構來統計員工，有四種操作 1. 加入一個初始工資為A的員工 2. 將所有人工資提高一個數 3. 將所有人工資降低一個數 4. 詢問第K多工資的員工是誰。 其間一點某人的工資低于工資下限，就會立刻離開公司...
吐槽：
1. 我不是新八... 我不會吐槽...
2. 用任何平衡樹寫都好.... 我是用來練splay的~~~(鄙視我這個弱菜有意思么)
3. 為毛剛進公司就離開的人不需要統計.... 題目里面也沒說啊... 害得我查了一晚上... 最后在插入的時候加個判斷就過了...
思路解析：
插入和查詢就是splay的基本操作了~
刪除半區間我是把(工資下限-1)插入到splay當中再旋到樹根(splay經典操作)然后刪除左子樹和樹根。
工資的升降可以直接更改工資下限，將更改的總量記錄一下~
splay可以只寫zig和zig-zig操作，zig-zag可以歸約掉... Orzzzzzz...... 一下子好寫了很多
維護size域我是從下到上維護的...因為需要更新size的只有x的直系祖先，所以旋到樹根的過程相當于更新了...
我終于會寫splay了... 好高欣~
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 using namespace std;
5 #define re(i,n) for(int i =0; i< n; i++)
6 const int N = 100005;
7 const int inf = ~0u>>2;
8 int sum,splaysz,temp;
9 // template 
10 struct node {
11 int p,chd[2],sz,mul,v;
12 node(
int P=0,
int val=0){
13 chd[0] = chd[1] = 0; sz = 0; mul = 1;
14 p = P, v = val;
15 }
16 } tree[N];
17 inline
void sc(
int y,
int x,
int p){tree[y].chd[p] = x, tree[x].p = y;}
18 inline
void upd(
int x){ tree[x].sz = tree[tree[x].chd[0]].sz + tree[tree[x].chd[1]].sz+tree[x].mul;}
19 inline
void rot(
int x){
20 int y = tree[x].p;
21 int w = tree[y].chd[1] == x;
22 sc(tree[y].p,x,tree[tree[y].p].chd[1] == y);
23 sc(y,tree[x].chd[w^1], w);
24 sc(x,y,w^1);
25 upd(y); upd(x);
26 }
27 void splay(
int x,
int rt){
28 while(tree[x].p != rt){
29 int y = tree[x].p;
30 int w = tree[y].chd[1] == x;
31 if(tree[y].p != rt && tree[tree[y].p].chd[w] == y) rot(y);
32 rot(x);
33 }
34 }
35 // operate
36 void ins(
int val){
37 if(tree[0].chd[0] == 0) {tree[++splaysz] = node(0,val); tree[0].chd[0] = splaysz; upd(splaysz);
return;}
38 int now = tree[0].chd[0];
39 while(1){
40 if(val == tree[now].v){
41 tree[now].mul++;
42 upd(now);
43 splay(now,0);
44 return ;
45 }
46 int w = val > tree[now].v;
47 if(tree[now].chd[w]) now = tree[now].chd[w];
48 else {
49 tree[++splaysz] = node(now,val); tree[now].chd[w] = splaysz;
50 upd(splaysz);
51 splay(splaysz,0);
52 return ;
53 }
54 }
55 }
56 void find(
int pos,
int k){
57 if (tree[pos].sz < k) {
58 puts("-1");
59 return ;
60 }
61 int x = tree[pos].chd[0];
62 if(tree[x].sz>=k) find(x,k);
63 else if(tree[x].sz + tree[pos].mul>=k) {
64 printf("%d\n",tree[pos].v-temp);
65 }
66 else find(tree[pos].chd[1], k - tree[x].sz - tree[pos].mul);
67 }
68 void del(){
69 int r = tree[0].chd[0];
70 int x = tree[r].chd[1];
71 sum += tree[r].sz - tree[x].sz -1;
72 tree[x].p = 0 , tree[0].chd[0] = x;
73 }
74 // main
75 int main(){
76 int n,m,x;
77 char ch[10];
78 while(cin >>n >>m){
79 sum = temp = splaysz = 0;
80 tree[0] = node(0,inf);
81 re(i,n){
82 scanf("%s%d",ch,&x);
83 switch(ch[0]){
84 case 'I' :
85 if(x >= m)
86 ins(x + temp);
87 break;
88 case 'S' :
89 temp += x;
90 ins(m + temp-1); del();
91 break;
92 case 'A' :
93 temp -= x;
94 break;
95 case 'F' :
96 if(tree[tree[0].chd[0]].sz < x) puts("-1");
97 else find(tree[0].chd[0],tree[tree[0].chd[0]].sz - x + 1);
98 break;
99 }
100 }
101 printf("%d\n",sum);
102 }
103 }
104
posted on 2012-05-01 19:52
西月弦 閱讀(1703)
評論(1) 編輯 收藏 引用 所屬分類:
解題報告 、
經典題目