GYM 101064 2016 USP Try-outs G. The Declaration of Independence 主席树

In 1776, a Committee of Five was chosen to draft the Declaration of Independence of the USA, among them John Adams, Thomas Jefferson and Benjamin Franklin. From June 11 to July 5 they worked tirelessly to write such important document.

It wasn't written correctly in the first attempt, and many many changes had to be made. Since in that time there weren't such great and time-saving utilities like git and version control, they had a very simple but time consuming way to keep old versions of the document.

Suppose Thomas Jefferson wanted to add a line to a version i of the document. Instead of changing the actual document in version i, he would use a letter copying press, a machine just invented by James Watt just around that time, to copy the version i to a new sheet of paper, and then would modify this new sheet of paper. This paper would then be stored so it could be copied later. As each modification creates a new version of the document, the kth modification will create the version k of the document. You can assume the version 0 of the document is an empty piece of paper.

As everything was written in ink and the committee doesn't like to contradict itself, each modification could only add some lines to the end of the document, or erase some lines from the beginning of the document.

Your task is to simulate the making of the Declaration of Independence. Each sentence is represented as an integer number. You need to process the following queries:

E v x — Copy the document with version v, then add sentence x to the end of the copied document
D v — Copy the document with version v, then remove the first sentence of the copied document

Queries are numbered from one. The document with version 0 is empty.

Input

In the first line an integer Q, the number of queries. Each of the next Q lines has a query, in the format given in the statement.

Limits

1 ≤ Q ≤ 105
In the ith query it is guaranteed that 0 ≤ v < i
For each query of type E, x will fit in a 32-bit signed integer
For each query of type D, it is guaranteed the document will not be empty during the removal of the first sentence

Output

For each query of type D, print the sentence removed.

Example
input
8
E 0 10
E 0 -10
D 2
D 1
E 2 5
D 5
D 6
D 2
output
-10
10
-10
5
-10

题意：q个操作，你需要在i是一个队列；

　　　E v x 表示在第v个队列插入x，形成第i个队列；

　　　D v 表示去掉v的对头，形成第i个队列；

思路：主席树，利用线段树第i个点，存储队列第（i-对头的位置）个元素的大小；

　　　利用L,R数组表示这个队列的左端在L[i],右端在R[i]的位置；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=1e5+10,M=1e6+10,inf=1e9+10;
const ll INF=1e18+10,mod=1e9+7;
struct SGT
{
    int ls[N*20],rs[N*20],rt[N*20],L[N*20],R[N*20],num[N*20];
    int tot;
    void init()
    {
        tot=0;
        memset(num,0,sizeof(num));
        memset(ls,0,sizeof(ls));
        memset(rs,0,sizeof(rs));
        memset(rt,0,sizeof(rt));
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
    }
    void build(int l,int r,int &pos)
    {
        pos=++tot;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(l,mid,ls[pos]);
        build(mid+1,r,rs[pos]);
    }
    void update(int rt,int p,int c,int l,int r,int &pos)
    {
        pos=++tot;
        ls[pos]=ls[rt];
        rs[pos]=rs[rt];
        if(l==r)
        {
            num[pos]=c;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid)update(ls[rt],p,c,l,mid,ls[pos]);
        else update(rs[rt],p,c,mid+1,r,rs[pos]);
    }
    int query(int p,int l,int r,int pos)
    {
        if(l==r) return num[pos];
        int mid=(l+r)>>1;
        if(p<=mid)return query(p,l,mid,ls[pos]);
        else return query(p,mid+1,r,rs[pos]);
    }
}tree;
char a[10];
int main()
{

    int q;
    scanf("%d",&q);
    //tree.init();
    tree.build(1,q,tree.rt[0]);
    tree.L[0]=1;
    tree.R[0]=0;
    for(int i=1;i<=q;i++)
    {
        scanf("%s",a);
        if(a[0]=='E')
        {
            int v,x;
            scanf("%d%d",&v,&x);
            tree.L[i]=tree.L[v];
            tree.R[i]=tree.R[v];
            tree.update(tree.rt[v],++tree.R[i],x,1,q,tree.rt[i]=tree.rt[v]);
        }
        else
        {
            int v;
            scanf("%d",&v);
            tree.L[i]=tree.L[v];
            tree.R[i]=tree.R[v];
            //cout<<tree.L[v]<<" "<<tree.R[v]<<endl;
            printf("%d
",tree.query(tree.L[i]++,1,q,tree.rt[i]=tree.rt[v]));
        }
    }
    return 0;
}
/*

8
E 0 10
E 0 -10
D 2
D 1
E 2 5
D 5
D 6
D 2

*/