首页 > 代码库 > Bzoj1503--Noi2004郁闷的出纳员
Bzoj1503--Noi2004郁闷的出纳员
treap乱搞一下
对于工资的加减不直接修改的点的值或打标记，而是维护一个外围的delta，这样维护也很方便
剩下删除和插入都是基本操作了
另： linux下rand（）的返回值是1-2^31-1，虽然感觉没什么关系，交上去就会被卡T掉。。。取个模就过了
代码：
#include<bits/stdc++.h>#define MAXN 100205#define MAXM 3005#define INF 1000000000#define MOD 998244353#define LL long longusing namespace std;inline int read() { int ret=0,f=1;char c=getchar(); while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1; c=getchar();} while(c<=‘9‘&&c>=‘0‘) {ret=ret*10+c-‘0‘;c=getchar();} return ret*f;}int n,m,delta;struct node{ int son[2],s,v,r,par,sz;}x[MAXN];struct Treap{ int L,R,root,away,cnt; void init() { L=0;R=1;root=MAXN-5;away=0;cnt=0; x[MAXN-5].r=INF;x[MAXN-5].v=INF; } inline void rotate(int num,int p) { int pa=x[num].par,t=x[num].sz; x[x[pa].par].son[x[x[pa].par].son[L]==pa?L:R]=num; x[num].sz=x[pa].sz;x[pa].sz-=t-x[x[num].son[p]].sz; x[pa].son[p^1]=x[num].son[p];if(x[num].son[p]) {x[x[num].son[p]].par=pa;} x[num].son[p]=pa;x[num].par=x[pa].par;x[pa].par=num; } void Insert(int v) { x[++cnt].v=v;x[cnt].r=rand()%1000007;x[cnt].s=1;x[cnt].sz=1; int now=root,pre; while(true) { if(v==x[now].v) {x[now].s++;x[now].sz++;cnt--;return;} pre=v<x[now].v?R:L;x[now].sz++; if(!x[now].son[pre]) {x[now].son[pre]=cnt;x[cnt].par=now;break;} now=x[now].son[pre]; } now=cnt; while(true) { if(x[x[now].par].son[L]==now) pre=R;else pre=L; if(x[now].r>x[x[now].par].r) rotate(now,pre); else break; } } void Del(int num) { while(x[num].son[L]) rotate(x[num].son[L],R); int now=x[num].par,pre=x[x[num].par].son[L]==num?L:R; while(now) {x[now].sz-=x[num].sz;now=x[now].par;} away+=x[num].sz;x[x[num].par].son[pre]=0; } void Check(int v) { int now=root,ed; while(true) { while(x[now].son[R]) now=x[now].son[R]; if(x[now].v<v) Del(now); else break; now=root; } } int Qurey(int k) { int now=root; if(k>x[root].sz) return -1; while(true) { if(x[x[now].son[L]].sz>=k-x[now].s&&x[x[now].son[L]].sz<k) return x[now].v; if(x[x[now].son[L]].sz<k) {k-=x[now].s+x[x[now].son[L]].sz;now=x[now].son[R];} else now=x[now].son[L]; } } int Finish() {return away;}};int main() { srand(2333333); n=read();m=read(); Treap p;char q[10];int k,ret; p.init(); for(int i=1;i<=n;i++) { scanf("%s",q);k=read(); if(q[0]==‘I‘) if(k>=m) p.Insert(k+delta); if(q[0]==‘A‘) delta-=k; if(q[0]==‘S‘) {delta+=k;p.Check(m+delta);} if(q[0]==‘F‘) { ret=p.Qurey(k); printf("%d\n",ret-(ret==-1?0:delta)); } } printf("%d\n",p.Finish()); return 0;}
Bzoj1503--Noi2004郁闷的出纳员
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。