NOI2004郁闷的出纳员
输入描述 Input Description
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
名称 格式 作用 I命令 I_k 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。 A命令 A_k 把每位员工的工资加上k S命令 S_k 把每位员工的工资扣除k F命令 F_k 查询第k多的工资 _（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。
输出描述 Output Description
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
样例输入 Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
样例输出 Sample Output
10
20
-1
2
代码
treap
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> using namespace std; struct data{ int l,r,num,rnd,s; }tr[100001]; int n,mn; int root,size,leave,delta; void update(int k){tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;} void rturn(int &k) { int t=tr[k].l; tr[k].l=tr[t].r; tr[t].r=k; tr[t].s=tr[k].s; update(k); k=t; } void lturn(int &k) { int t=tr[k].r; tr[k].r=tr[t].l; tr[t].l=k; tr[t].s=tr[k].s; update(k); k=t; } void insert(int &k,int x) { if(k==0) { size++;k=size; tr[k].rnd=rand(); tr[k].num=x; tr[k].s=1; return; } tr[k].s++; if(x<tr[k].num) { insert(tr[k].l,x); if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k); } else { insert(tr[k].r,x); if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k); } } int del(int &k,int x) { int t; if(k==0)return 0; if(tr[k].num<x) {t=tr[tr[k].l].s+1;k=tr[k].r;return t+del(k,x);} else {t=del(tr[k].l,x);tr[k].s-=t;return t;} } int find(int k,int x) { if(tr[tr[k].l].s+1==x)return tr[k].num+delta; else if(tr[tr[k].l].s+1<x)return find(tr[k].r,x-tr[tr[k].l].s-1); else return find(tr[k].l,x); } int main() { srand(time(0)); scanf("%d%d",&n,&mn); char ch[1];int x; while(n--) { scanf("%s%d",ch,&x); if(ch[0]=='I')if(x>=mn)insert(root,x-delta); if(ch[0]=='A')delta+=x; if(ch[0]=='S'){delta-=x;leave+=del(root,mn-delta);} if(ch[0]=='F') { if(x>tr[root].s)printf("-1"); else printf("%d",find(root,tr[root].s-x+1)); printf("\n"); } } printf("%d",leave); return 0; } |
splay
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<iostream> #include<cstdio> using namespace std; struct data{ int l,r,f,s,v,num; }tr[100001]; int n,m,l,tot,root,delta; void pushup(int x){tr[x].s=tr[tr[x].l].s+tr[tr[x].r].s+1;} void zig(int &x) { int y=tr[x].f; int z=tr[y].f; if(y==tr[z].l)tr[z].l=x; else tr[z].r=x; tr[x].f=z; tr[y].l=tr[x].r; tr[tr[x].r].f=y; tr[x].r=y; tr[y].f=x; pushup(y); pushup(x); if(y==root)root=x; } void zag(int &x) { int y=tr[x].f; int z=tr[y].f; if(y==tr[z].l)tr[z].l=x; else tr[z].r=x; tr[x].f=z; tr[y].r=tr[x].l; tr[tr[x].l].f=y; tr[y].f=x; tr[x].l=y; pushup(y); pushup(x); if(y==root)root=x; } void splay(int &x,int d) { while(tr[x].f!=d) { if(tr[tr[x].f].l==x)zig(x); else zag(x); } } void insert(int k) { if(!root) { root=++tot; tr[tot].num=k; tr[tot].s=1; return; } int p=root,z; while(p) { z=p; ++tr[p].s; if(k<tr[p].num)p=tr[p].l; else p=tr[p].r; } if(tr[z].num>k)tr[z].l=++tot; else tr[z].r=++tot; tr[tot].num=k;tr[tot].s=1;tr[tot].f=z; splay(tot,0); } int find(int x,int k) { if(k<=tr[tr[x].r].s)return find(tr[x].r,k); if(k==tr[tr[x].r].s+1)return tr[x].num; return find(tr[x].l,k-tr[tr[x].r].s-1); } int dec(int &x,int f) { if(!x)return 0; int k; if(tr[x].num+delta<m) { k=dec(tr[x].r,x)+tr[tr[x].l].s+1; tr[tr[x].r].s=tr[x].s-k; x=tr[x].r;tr[x].f=f; } else { k=dec(tr[x].l,x); tr[x].s-=k; } return k; } int main() { scanf("%d%d",&n,&m); while(n--) { char c[1]; int k; scanf("%s%d",&c,&k); if(c[0]=='I'&&k>=m)insert(k-delta); if(c[0]=='F')printf("%d\n",k<=tr[root].s?find(root,k)+delta:-1); if(c[0]=='A')delta+=k; if(c[0]=='S'){delta-=k;l+=dec(root,0);} } printf("%d\n",l); return 0; } |
线段树 感谢hjz提供的思路
下面的代码比较丑的部分是我写的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <cstdio> #include <cstring> #define I 100000 using namespace std; struct data { int l,r,num; bool cuted; }t[1200001]; int n,gz,change=0,ans=0,fans,gain; void build_tree(int x,int L,int R) { t[x].l=L;t[x].r=R; if(L==R)return; int mid=(L+R)>>1; build_tree(x<<1,L,mid); build_tree(x<<1|1,mid+1,R); } void add_tree(int x,int y) { int l=t[x].l,r=t[x].r; if(l==r){t[x].num++;return;} int mid=(l+r)>>1; if(y<=mid)add_tree(x<<1,y); else add_tree(x<<1|1,y); t[x].num=t[x<<1].num+t[x<<1|1].num; } void pushup(int k,int x){while(k>1){k>>=1;t[k].num-=x;}} void pushdown(int k) { int l=t[k].l,r=t[k].r; t[k].num=0; t[k].cuted=1; if(l!=r){pushdown(k<<1);pushdown(k<<1|1);} } void cut_tree(int x,int R) { if(R>=t[x].r) { ans+=t[x].num; pushup(x,t[x].num); pushdown(x); return; } if(R>=t[x<<1|1].l)cut_tree(x<<1|1,R); cut_tree(x<<1,R); } void inquiry_tree(int x) { if(!t[x].num)return; if(t[x].num<gain){gain-=t[x].num;return;} if(t[x].l==t[x].r) { if(gain<=t[x].num) { fans=t[x].l; gain=0; } return; } inquiry_tree(x<<1|1); if(gain)inquiry_tree(x<<1); } int main() { scanf("%d%d",&n,&gz); char ch[1];int x; build_tree(1,gz-I,I<<1); while(n--) { scanf("%s%d",ch,&x); if(ch[0]=='I') { if(x>=gz) add_tree(1,x-change); } else if(ch[0]=='F') { gain=x; fans=-1; inquiry_tree(1); if(fans!=-1)fans+=change; printf("%d\n",fans); } else if(ch[0]=='S') { change-=x; cut_tree(1,gz-change-1); } else change+=x; } printf("%d\n",ans); return 0; |
计数器 9786956
OI 课件=>
OI 课件=>
您的treap貌似也写错了……也没处理相同的情况
好像是有问题
关于splay。。相同的n个值会开出n个节点，这样不会出现一些奇葩错误么0.0，不是应该开mul变量来记录当前值的出现次数么TAT
这个splay还是别看了，我不知道从哪抄来的，去年这个时候我就一傻逼（虽然现在好不了多少）
唔 才不说splay第一个姿势就是从您营业额统计里学来的呢
千万别学zig，zag就好了
treap中的srand（）用time（0）在BZOJ上会RE的！！！随便用个数即可
treap把左右子树换成大小为二的数组记录 旋转操作可以少写一个 于是就可以使代码更短