本文共 4378 字，大约阅读时间需要 14 分钟。
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工 作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把 他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。接下来的n行，每行表示一条命令。
输出的行数为F命令的条数加一。
9 10
10
数据范围：
NOI2004 ，平衡树
维护一个动态数列,求第K大,,.其实没必要用到动态修改,每次都是对所有员工修改,因此只需要记录detal,1:每次Insert()加入相对值k-det,
每次减少det,执行删除操作,找到第一个节点>=minn-det的值,旋转至跟,删除左子树就是答案
Bug:由于细节比较多,因此在码代码的时候一定要细心.
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #define ll long long 15 #define rep(i,a,b) for(register int i=a;i<=b;i++) 16 #define inf 1<<30 17 #define il inline 18 #define RG register 19 using namespace std; 20 const int N=100010; 21 int fa[N],ch[N][2],key[N],cnt[N],size[N],q,mini,det,root,tot,ans; 22 il int gi(); 23 il void Newnode(int fu,int v) { 24 tot++;// bug 25 fa[tot]=fu; 26 size[tot]=cnt[tot]=1; 27 key[tot]=v; 28 } 29 il void clear(int x) { 30 fa[x]=ch[x][1]=ch[x][0]=key[x]=size[x]=cnt[x]=0; 31 } 32 il int getx(int x) { 33 return ch[fa[x]][1]==x; 34 } 35 il void Update(int x) { 36 if(x) { 37 size[x]=cnt[x]; 38 if(ch[x][0]) size[x] += size[ch[x][0]]; 39 if(ch[x][1]) size[x] += size[ch[x][1]]; 40 } 41 } 42 il void Rotate(int x) { 43 int old=fa[x],oldx=fa[fa[x]],bj=getx(x); 44 ch[old][bj]=ch[x][!bj] , fa[ch[old][bj]]=old ; 45 ch[x][!bj]=old;fa[old]=x; 46 fa[x]=oldx; 47 if(oldx) ch[oldx][ch[oldx][1]==old]=x;// bug getx(old) -> getx(ch[oldx][1]==old)// 因为变了 48 Update(old),Update(x); 49 } 50 il void Splay(int x,int goal) { 51 while(fa[x]!=goal) { 52 if(fa[fa[x]]==goal) Rotate(x); 53 else { 54 int od=getx(x),po=getx(fa[x]); 55 if(od==po) Rotate(fa[x]),Rotate(x); 56 else Rotate(x),Rotate(x); 57 } 58 } 59 if(goal==0) root=x; 60 } 61 il void Insert(int x) { 62 if(root==0) { 63 Newnode(0,x); 64 root=tot; 65 return; 66 } 67 int now=root,fu=0; 68 while(1) { 69 if(x==key[now]) { 70 cnt[now]++;Update(now);Update(fu);// cnt[x]++ - > cnt[now]++; 71 Splay(now,0);// bug Splay(now,0); 72 return; 73 } 74 fu=now; 75 now=ch[now][x > key[now]]; 76 if(now==0) { 77 Newnode(fu,x); 78 ch[fu][x>key[fu]]=tot;// bug key[now] x> key[fa] 79 Update(fu); 80 Splay(tot,0);// bug Splay(now,0) - > Splay (tot,0); 81 return; 82 } 83 } 84 } 85 il int find(int x) { 86 int now=root;RG int tmp; 87 while(1) { 88 if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0]; 89 else { 90 tmp = (ch[now][0] ? size[ch[now][0]] : 0) + cnt[now]; 91 if(x<=tmp) return key[now]; 92 x-=tmp;now=ch[now][1]; 93 } 94 } 95 } 96 void Del() { 97 if(root==0) return;// 98 int k=mini-det; 99 int now=root,st=-1;100 while(1) {101 if(key[now]>=k) {102 if(st!=-1) st = key[now] < key[st] ? now : st;103 else st=now;104 }105 now=ch[now][k > key[now]];106 if(now==0) {107 if(st!=-1) {108 Splay(st,0);109 size[st] -= size[ch[st][0]];110 ans+=size[ch[st][0]];111 ch[st][0]=0;112 }113 else {114 // 整颗都要删除115 ans+= size[root];116 clear(root);117 root=0;118 }119 return;120 }121 }122 }123 int main() {124 freopen("Splay.in","r",stdin);125 freopen("Splay.out","w",stdout);126 q=gi(),mini=gi();127 char s[3];RG int k;128 while(q--) {129 scanf("%s",s);k=gi();130 switch(s[0]) {131 case 'I' :if(k '9')&&ch!='-') ch=getchar();145 if(ch=='-') ch=getchar(),f=-1;146 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();147 return res*f;148 }
转载于:https://www.cnblogs.com/ypz999/p/6674023.html