星际争霸

题目描述

玩星际争霸时，我们常常会不顾一切地大肆建造军队以扩充自己的战斗力。当我们快速建造军队时，我们总想知道这支部队的战斗力，以便设计好战略。你的任务是设计出一个能够快速回答一支部队的战斗力强弱的程序，部队的战斗力就是部队的人数。

C num，往编号为num的部队里加一个兵，如果当前还没有编号为num的部队，则建立这支部队并添加一个兵；
D num，代表编号为num的部队里一个兵牺牲了，如果此时部队里没有兵了，则删掉此部队，如果没有编号为num的部队，忽略此操作。
M x<y，表示将y里面的兵合并到x中，然后y消失，如果x或者y中任意一个数不存在，则忽略此次操作。
其中0<x,y,num<10^12

问：有n(<=600000)条命令，m<=100000组询问，每次询问请输出第k大值。

输入

第一行为一个整数n，表示后面的操作命令总数

从第二行开始的后n行，每行是一条操作命令

第n+2行是一个整数m，表示有m个提问

第n+3行有m个用一个空格隔开的树k1，k2，k3.。。。km，也就是提问站头里第ki强的部队编号。注意：可能ki=kj，也就是说战斗力第k强可能被问到两次

输出

输出jm行，每行输出一个战斗力第ki强的部队的士兵人数，如果没有第ki强的部队，则输出“NO”。

如果士兵人数从大到小分别为7，5，5，3，2，则战斗力第一强大的是7，第二，第三都为5，第四位3，第五为2

样例输入

5 C 4 C 8 M 8<4 D 4 C 5 3 1 2 3

样例输出

2 1

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
long long hehe[700045],cnt;
struct node
{
    long long key,lev,num;
    node *child[2];
} Treap[700045],*root,*pos;
queue<node*>mem;
long long read()
{
    long long 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*10+ch-'0';
        ch=getchar();
    }
    ungetc(ch,stdin);
    return x*f;
}
void Newnode(node*&r,int key)
{
    if(mem.empty())
        r=pos++;
    else
        r=mem.front(),mem.pop();
    r->key=key;
    r->lev=rand();
    r->num=1;
    r->child[0]=r->child[1]=0;
}
void roll(node*&r,bool t)
{
    node*y=r->child[!t];
    r->child[!t]=y->child[t];
    y->child[t]=r;
    r=y;
}
void insert(node*&r,int key)
{
    if(!r)
        Newnode(r,key);
    else
    {
        bool t=r->key<key;
        insert(r->child[t],key);
        if(r->child[t]->lev<r->lev)
            roll(r,!t);
    }
}
void Delete(node*&r,int key)
{
    if(!r)
        return;
    if(r->key==key)
    {
        if(r->child[0]&&r->child[1])
        {
            bool t=r->child[0]->lev<r->child[1]->lev;
            roll(r,t);
            Delete(r->child[t],key);
        }
        else
        {
            mem.push(r);
            if(r->child[0])
                r=r->child[0];
            else
                r=r->child[1];
        }
    }
    else
        Delete(r->child[r->key<key],key);
}
node*find(node*r,int key)
{
    if(!r)
        return NULL;
    if(r->key==key)
        return r;
    else return find(r->child[r->key<key],key);
}
void print(node*r)
{
    if(!r)
        return;
    print(r->child[0]);
    if(r->num!=0)
        hehe[++cnt]=r->num;
    print(r->child[1]);
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n,m,k1,k2;
    char lol[145];
    cin>>n;
    getchar();
    pos=Treap;
    for(int i=1; i<=n; i++)
    {
        char ch=getchar();
        while(ch!='C'&&ch!='D'&&ch!='M')
        ch=getchar();
        if(ch=='C')
        {
            long long s=read();
            node*p=find(root,s);
            if(p==0)
                insert(root,s);
            else
                p->num++;
        }
        if(ch=='D')
        {
            long long s=read();
            node*p=find(root,s);
            if(p==0)
                continue;
            else
            {
                p->num--;
                if(p->num==0)
                    Delete(root,s);
            }
        }
        if(ch=='M')
        {
            long long k1=read(),k2=read();
            node*p1=find(root,k1);
            node*p2=find(root,k2);
            if(p1==0||p2==0)
                continue;
            p1->num+=p2->num;
            Delete(root,k2);
        }
    }
    print(root);
    sort(hehe+1,hehe+1+cnt,cmp);
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        long long s=read();
        if(s<=cnt)
            printf("%d
",hehe[s]);
        else
            printf("NO
");
    }
    return 0;
}

PEACE