[codevs1286] [BZOJ1503] 답답한 출납원, splay 연습

전송문1전송문2는 앞에 쓰여있다. 코드가 길면 세부적인 문제가 많아진다. 역시 숙련이 필요하다. 사고방식: 삽입, 삭제, k번 큰 splay를 찾고 개치 함수를 추가한다. 임금을 바꾸는 조작이 적기 때문에 직접 폭력은 뿌리부터 아래로 바꾸고 임금 하한선보다 작으면 입대한다.마지막으로 팀의 요소를 삭제하면 됩니다. 주의하세요. 처음에 월급이 하한선보다 적은 사람은 회사에 들어오지 않지만 회사를 떠난 인원도 계산하지 않습니다. 기억하세요!코드:

#include<bits/stdc++.h>
using namespace std;
int root,n,minn,tot,ans,x;
char ch;
queue<int> q;
struct os
{
    int occ,data,fa,sz,ch[2];
}a[100100];
void ct(int now)
{
    a[now].sz=a[now].occ+a[a[now].ch[0]].sz+a[a[now].ch[1]].sz;
}
void made(int x)
{
    a[++tot].data=x;
    a[tot].occ=a[tot].sz=1;
}
void rorate(int now,bool x)
{
    int pa=a[now].fa;
    a[a[now].fa].ch[x^1]=a[now].ch[x];
    if (a[now].ch[x])a[a[now].ch[x]].fa=pa;
    a[now].fa=a[pa].fa;
    if (a[pa].fa) 
    {
        if (a[a[pa].fa].ch[0]==pa) a[a[pa].fa].ch[0]=now;
        else a[a[pa].fa].ch[1]=now;
    }
    a[pa].fa=now;
    a[now].ch[x]=pa;
    ct(pa);
    ct(now);
}
void splay(int now,int goal)
{
    int pa;
    while (a[now].fa!=goal)
    {
        pa=a[now].fa;
        if (a[pa].fa==goal)
        {
            if (a[pa].ch[0]==now) rorate(now,1);
            else rorate(now,0);
        }
        else if (a[a[pa].fa].ch[0]==pa)
        {
            if (a[pa].ch[0]==now) rorate(pa,1);
            else rorate(now,0);
            rorate(now,1);
        }
        else
        {
            if (a[pa].ch[1]==now) rorate(pa,0);
            else rorate(now,1);
            rorate(now,0);
        }
    }
    if (!goal) root=now; 
}
void insert(int x)
{
    if (!root) {made(x);root=tot;return;}
    int now=root,flag=1;
    while (flag)
    {
        a[now].sz++;
        if (a[now].data==x){a[now].occ++;splay(now,0);return;}
        else if (a[now].data>x)
        {
            if (!a[now].ch[0]) made(x),a[now].ch[0]=tot,a[tot].fa=now,flag=0;
            else now=a[now].ch[0];
        }
        else
        {
            if (!a[now].ch[1]) made(x),a[now].ch[1]=tot,a[tot].fa=now,flag=0;
            else now=a[now].ch[1];
        }
    }
    splay(tot,0);
}
void update(int now,int x)
{
    if (!now) return;
    a[now].data+=x;
    if (a[now].data<minn) q.push(now);
    update(a[now].ch[0],x);
    update(a[now].ch[1],x);
}
int Kth(int k)
{
    if (k<=0) return 0;
    int now=root;
    while (now)
    {
        if (a[a[now].ch[1]].sz<k&&a[a[now].ch[1]].sz+a[now].occ>=k) break;
        if (a[a[now].ch[1]].sz>=k) now=a[now].ch[1];
        else k-=(a[a[now].ch[1]].sz+a[now].occ),now=a[now].ch[0];
    }
    if (now) splay(now,0);
    return now;
}
int find_max(int now)
{
    if (!now) return 0;
    while (now)
    {
        if (!a[now].ch[1]) return now;
        else now=a[now].ch[1];
    }
}
bool del(int now)
{
    if (!now) return 0;
    splay(now,0);
    if (!a[now].ch[0]&&!a[now].ch[1]) root=0;
    else if (!a[now].ch[1])
    {
        root=a[now].ch[0];
        a[a[now].ch[0]].fa=0;
    }
    else if (!a[now].ch[0])
    {
        root=a[now].ch[1];
        a[a[now].ch[1]].fa=0;
    }
    else
    {
        splay(find_max(a[now].ch[0]),root);
        root=a[now].ch[0];
        a[a[now].ch[0]].fa=0;
        a[a[now].ch[1]].fa=a[now].ch[0];
        a[a[now].ch[0]].ch[1]=a[now].ch[1];
        ct(a[now].ch[0]);
    }
    return 1;
}
main()
{
    scanf("%d%d",&n,&minn);
    a[0].data=-1;
    while (n--)
    {
        ch=getchar();
        while (ch!='I'&&ch!='A'&&ch!='S'&&ch!='F') ch=getchar();
        scanf("%d",&x);
        if (ch=='I')
        {
            if (x>=minn) insert(x);
        }
        else if (ch=='A') update(root,x);
        else if (ch=='S') 
        {
            update(root,-x);
            while (!q.empty())
            ans+=a[q.front()].occ,
            del(q.front()),
            q.pop();
        }
        else printf("%d
",a[Kth(x)].data);
    }
    printf("%d",ans);
}