Description

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内

Solution

考虑到太久没有写\(Splay\)，就练习一波

果然是调了很久，忘记更新\(rt\)，然后\(pushdown\)也不及时

Code 

#include
    
     #define ll long longusing namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005class SplayTree {    private:        int c[MN][2],fa[MN],cnt[MN],siz[MN],val[MN],lazy[MN],rt,sz;        inline void up(int x){siz[x]=siz[c[x][1]]+siz[c[x][0]]+cnt[x];}        inline void down(int x)        {            if(lazy[x]==0) return;            if(c[x][1]) lazy[c[x][1]]+=lazy[x],val[c[x][1]]+=lazy[x];            if(c[x][0]) lazy[c[x][0]]+=lazy[x],val[c[x][0]]+=lazy[x];            lazy[x]=0;        }        #define get(x) (c[fa[x]][1]==x)        inline void rotate(int x)        {            register int y=fa[x],z=fa[y],l=get(x),r=l^1;            if(z) c[z][get(y)]=x;fa[x]=z;c[y][l]=c[x][r];fa[c[x][r]]=y;c[x][r]=y;fa[y]=x;up(y);        }        inline void Splay(int x,int k=0)        {            for(;fa[x]!=k;rotate(x))                if(fa[fa[x]]!=k) rotate((get(x)^get(fa[x])?x:fa[x]));            if(!k) rt=x;up(x);        }        inline void Output(int x)        {            down(x);            if(c[x][0]) Output(c[x][0]);            for(int i=1;i<=cnt[x];++i)printf("%d ",val[x]);            if(c[x][1]) Output(c[x][1]);        }        inline void Del(int v)        {            register int x=rt,p=0;            for(down(x);x&&val[x]!=v;siz[x]--,p=x,x=c[x][v>val[x]],down(x));            if(x)            {                if(cnt[x]>1){cnt[x]--;Splay(x);return;}                register int tmp;                if(!(c[x][0]*c[x][1]))                {                    if(p) c[p][v>val[p]]=c[x][0]|c[x][1];                    if(c[x][0]||c[x][1]) fa[c[x][c[x][1]!=0]]=p;                    if(rt==x) rt=c[x][0]|c[x][1];                    return;                }                for(tmp=c[x][1];c[tmp][0];tmp=c[tmp][0]);                Splay(x);Splay(tmp,rt);                c[tmp][0]=c[x][0];rt=tmp;fa[c[x][0]]=tmp;fa[tmp]=0;                up(tmp);return;            }        }        inline int find(int x,int k)        {            down(x);if(siz[x]
     
      <=0) return -1;            if(k<=siz[c[x][0]]) return find(c[x][0],k);            else if(k>siz[c[x][0]]+cnt[x]) return find(c[x][1],k-siz[c[x][0]]-cnt[x]);            else return x;        }    public:        int K,ans;        SplayTree(int _ans=0):ans(_ans){}        inline void output(){printf("Tree: ");Output(rt);puts("");}        inline void Insert(int v)        {            register int x=rt,p=0;            for(down(x);x&&val[x]!=v;p=x,x=c[x][v>val[x]],down(x));            if(x) cnt[x]++;            else            {                x=++sz;                if(p) c[p][v>val[p]]=x,fa[x]=p;                val[x]=v;cnt[x]=siz[x]=1;            }            Splay(x);        }        inline void Add(int x)        {            if(x>0) lazy[rt]+=x,val[rt]+=x;            else            {                register int p;                lazy[rt]+=x;val[rt]+=x;                while((p=find(rt,1))>0&&val[p]
      
       =T.K) T.Insert(x);        if(s[0]=='A') T.Add(x);        if(s[0]=='S') T.Add(-x);        if(s[0]=='F') T.Query(x);    //  T.output();    }    printf("%d\n",T.ans);    return 0;}
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！