[GDOI 시 뮬 레이 션 2016.03.05] 마도 연구

제목 의 대의
t 개 를 재 집합 할 수 있 는 Ti 를 지정 합 니 다. i 개 에서 전 i 대 를 재 집중 적 으로 선택 하여 재 집합 S 를 구성 할 수 있 습 니 다.m 개의 조작 이 있 는데 두 가지 로 나 뉘 는데 그것 이 바로 t 집합 에 특정한 요 소 를 삭제 하거나 t 집합 에 특정한 요 소 를 추가 하 는 것 이다.매번 조작 후 S 의 앞 n 대 를 유지 합 니 다.
m, n, t ≤ 300000, 모든 원 소 는 109 보다 크 지 않 은 정수 입 니 다.
제목 분석
분명히 우 리 는 데이터 구 조 를 이용 하여 T 집합 과 S 집합 을 유지 할 수 있다.동작 을 추가 할 때, 우 리 는 대응 하 는 Ti 집합 에 이 수 를 삽입 하여 랭 킹 을 조회 합 니 다.만약 rank < = i 가 하나의 수 를 밀 어 냈 다 는 것 을 설명 한다 면, 우 리 는 Ti 가 집합 한 i + 1 명 을 S 에서 삭제 하고 마지막 으로 S 에 새 수 를 추가 하면 됩 니 다.삭제 작업 이 유사 합 니 다.이 데이터 구 조 는 밸 런 스 트 리, 짝 짓 기 등 을 선택 할 수 있다.사실 가중치 선분 트 리 는 문 제 를 해결 할 수 있 고 구체 적 인 과정 은 동태 적 인 개방 점 이 필요 하 다.
코드 구현

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long LL;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch))
    {
        if (ch=='-')
            f=-1;
        ch=getchar();
    }
    while (isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

const int S=40000005;
const int N=300005;
const int M=300005;
const int T=300005;
const int P=1000000000;

int n,m;

struct tree
{
    int son[S][2],size[S];
    int root[T];
    LL sum[S];
    int tot;

    int newnode()
    {
        size[++tot]=0;
        son[tot][0]=son[tot][1]=sum[tot]=0;
        return tot;
    }

    void init()
    {
        memset(size,0,sizeof size);
        memset(sum,0,sizeof sum);
        memset(son,0,sizeof son);
        tot=0;
        for (int i=0;i<=300000;i++)
            root[i]=newnode();
    }

    int kth(int rt,int rk,int l,int r)
    {
        if (l==r)
            return l;
        int mid=l+r>>1;
        if (size[son[rt][1]]>=rk)
            return kth(son[rt][1],rk,mid+1,r);
        rk-=size[son[rt][1]];
        return kth(son[rt][0],rk,l,mid);
    }

    int rank(int rt,int x,int l,int r)
    {
        if (l==r)
            return 1;
        int mid=l+r>>1;
        if (x>mid)
            return rank(son[rt][1],x,mid+1,r);
        else
            return size[son[rt][1]]+rank(son[rt][0],x,l,mid);
    }

    int change(int rt,int x,int l,int r,int delta)
    {
        if (!rt)
            rt=newnode();
        if (l==r)
        {
            sum[rt]+=delta*1ll*x;
            size[rt]+=delta;
            return rt;
        }
        int mid=l+r>>1;
        if (x<=mid)
            son[rt][0]=change(son[rt][0],x,l,mid,delta);
        else
            son[rt][1]=change(son[rt][1],x,mid+1,r,delta);
        int ls=son[rt][0],rs=son[rt][1];
        sum[rt]=sum[ls]+sum[rs];
        size[rt]=size[ls]+size[rs];
        return rt;
    }

    LL query(int rt,int kth,int l,int r)
    {
        if (l==r)
            return l*1ll*min(kth,size[rt]);
        int mid=l+r>>1;
        if (kth<=size[son[rt][1]])
            return query(son[rt][1],kth,mid+1,r);
        else
            return sum[son[rt][1]]+query(son[rt][0],kth-size[son[rt][1]],l,mid);
    }
}t;

int main()
{
    freopen("grimoire.in","r",stdin);
    freopen("grimoire.out","w",stdout);
    n=read(),m=read();
    t.init();
    for (int i=1;i<=m;i++)
    {
        char cmd=getchar();
        while (!isalpha(cmd))
            cmd=getchar();
        int ti=read(),pi=read();
        if (cmd=='B')
        {
            t.change(t.root[ti],pi,1,P,1);
            int rk=t.rank(t.root[ti],pi,1,P);
            if (rk<=ti)
            {
                if (t.size[t.root[ti]]>ti)
                {
                    int num=t.kth(t.root[ti],ti+1,1,P);
                    t.change(t.root[0],num,1,P,-1);
                }
                t.change(t.root[0],pi,1,P,1);
            }
            LL ans=t.query(t.root[0],n,1,P);
            printf("%lld
",ans);
        }
        else
        {
            int rk=t.rank(t.root[ti],pi,1,P);
            t.change(t.root[ti],pi,1,P,-1);
            if (rk<=ti)
            {
                if (t.size[t.root[ti]]>=ti)
                {
                    int num=t.kth(t.root[ti],ti,1,P);
                    t.change(t.root[0],num,1,P,1);
                }
                t.change(t.root[0],pi,1,P,-1);
            }
            LL ans=t.query(t.root[0],n,1,P);
            printf("%lld
",ans);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}