题目

std:

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e6;
struct Node{
    int ls,rs;
    int val,pos;
}tr[MAXN*20*4];
int nodeCnt=0;
void insert(int &p,int l,int r,int x,int val){
    if(!p)p=++nodeCnt;
    if(l==r){
        tr[p].val+=val;
        tr[p].pos=l;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)insert(tr[p].ls,l,mid,x,val);
    else if(x>mid)insert(tr[p].rs,mid+1,r,x,val);
    tr[p].val=max(tr[tr[p].ls].val,tr[tr[p].rs].val);
    tr[p].pos=tr[tr[p].ls].val>=tr[tr[p].rs].val?tr[tr[p].ls].pos:tr[tr[p].rs].pos;
}
int merge(int p,int q,int l,int r){
//这么合并不会破坏原有两颗线段数吗
    if(!p)return q;
    if(!q)return p;
    if(l==r){
        tr[p].val+=tr[q].val;
        tr[p].pos=tr[p].val?l:0;
        return p;
    }
    int mid=(l+r)>>1;
    tr[p].ls=merge(tr[p].ls,tr[q].ls,l,mid);
    tr[p].rs=merge(tr[p].rs,tr[q].rs,mid+1,r);
    tr[p].val=max(tr[tr[p].ls].val,tr[tr[p].rs].val);
    tr[p].pos=tr[tr[p].ls].val>=tr[tr[p].rs].val?tr[tr[p].ls].pos:tr[tr[p].rs].pos;
    return p;
}
int roots[MAXN],rootCnt=0;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            roots[++rootCnt]=++nodeCnt;
        }else if(opt==2){
            int nowRoot,x,num;
            scanf("%d%d%d",&nowRoot,&x,&num);
            insert(roots[nowRoot],1,MAXN,x,num);//值域不是2e5吗
        }else if(opt==3){
            int nowRoot;
            scanf("%d",&nowRoot);
            cout<<tr[roots[nowRoot]].pos<<endl;
        }else if(opt==4){
            int root1,root2;
            scanf("%d%d",&root1,&root2);
            roots[++rootCnt]=merge(root1,root2,1,MAXN);
            //是不是应该写merge(roots[root1],roots[root2],1,MAXN)
        }
    }
    return 0;
}