题目简介:
用一个数据结构来统计员工,有四种操作 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
西月弦 阅读(1644)
评论(1) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目