本文主要是介绍bzoj 1503 郁闷的出纳员 (权值线段树或splay)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
思路：
因为工资修改值最多只有1e5，初始工资1e5+修改的2e5，那么其实我们只要开3e5的权值线段树就能维护了。对于加减钱，我们只要修改标准即可，对于加入人，只要让他的初始工资补上之前修改过得标准即可，而查询第k大，就是正常操作了。
为了方便操作，我们让初始工资钱成为1e5+1，就能保证钱始终为正了，这样清空线段树的时候就十分方便了。
splay刚刚开始学，等等补上splay写法（好像线段树能写很多平衡树问题。。。）
错误及反思：
如果新加入的人工资低于最低要求，就当这个人没来过。。。
代码：
权值线段树写法：
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N = 400000;
int segtree[N<<2],lazy[N<<2],n,mn,bz=0,tot=0;
void pushdown(int l,int r,int rt){if(lazy[rt]){lazy[rt<<1]=lazy[rt<<1|1]=1;segtree[rt<<1]=segtree[rt<<1|1]=0;lazy[rt]=0;}
}void add(int val,int l,int r,int rt){if(l==r){segtree[rt]++;return ;}pushdown(l,r,rt);int m=(l+r)/2;if(val<=m) add(val,lson);else add(val,rson);segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}void del(int L,int R,int l,int r,int rt){if(L<=l&&R>=r){segtree[rt]=0;lazy[rt]=1;return ;}pushdown(l,r,rt);int m=(l+r)/2;if(L<=m) del(L,R,lson);if(R>m) del(L,R,rson);segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}int query(int val,int l,int r,int rt){if(l==r) return l;pushdown(l,r,rt);int m=(l+r)/2;if(segtree[rt<<1]>=val) return query(val,lson);else return query(val-segtree[rt<<1],rson);
}
int main(){scanf("%d%d",&n,&mn);while(n--){char x[10]; int y;scanf("%s %d",x,&y);if(x[0]=='I'){if(y>=mn) tot++,add(y+100001+bz,1,350000,1);}else if(x[0]=='A') bz-=y;else if(x[0]=='S'){bz+=y;del(1,mn+bz+100000,1,350000,1);}else{del(1,mn+bz+100000,1,350000,1);if(segtree[1]>=y)printf("%d\n",query(segtree[1]-y+1,1,350000,1)-100001-bz);else printf("-1\n");}}printf("%d\n",tot-segtree[1]);
}
这篇关于bzoj 1503 郁闷的出纳员 (权值线段树或splay)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
