个人认为..配对堆最难的题了

考虑到tag可能会有很大影响,所以这时候需要想办法让tag尽可能的小

做法:

借鉴splay的做法,

每次做一个findroot操作以后,类似splay一样,把它沿路的分离出来,然后u一发

让堆的深度尽量小,这里不管是ch还是right都算一层深度

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct node
{
    int val;
    int tag;
    node * left;
    node * right;
    node * ch;
};
node * null;
node * new_node(int x=-999999999)
{
    static node a[600005];
    static int top=0;
    node * t=&a[top++];
    t->val=x;
    t->tag=0;
    t->left=null;
    t->right=null;
    t->ch=null;
    return t;
}
node * a[300005];
node * b[300005];
node * root;
node * join(node * x,node * y)
{
    if (x==null) return y;
    if (y==null) return x;
    if (x->val<y->val) swap(x,y);
    y->val-=x->tag;
    y->tag-=x->tag;
    y->left=x;
    y->right=x->ch;
    x->ch->val-=y->tag;
    x->ch->tag-=y->tag;
    x->ch->left=y;
    x->ch=y;
    return x;
}
node * u(node * x)
{
    if (x==null) return x;
    node * y;
    y=x->right;
    if (y==null) return x;
    y->tag+=x->tag;
    y->val+=x->tag;
    y->left=null;
    x->right=null;
    node * z=y->right;
    if (z==null) return join(x,y);
    z->tag+=y->tag;
    z->val+=y->tag;
    z->left=null;
    y->right=null;
    return join(u(z),join(x,y));
}
node * cur[300005];
int top=0;
node * dfs(node * x)
{
    if (x->left==null)
    {
        return x;
    }
    node * root=dfs(x->left);
    x->left->ch=x->right;
    x->right->left=x->left;
    x->right->tag+=x->tag;
    x->right->val+=x->tag;
    x->tag+=x->left->tag;
    x->val+=x->left->tag;
    x->left=null;
    x->right=null;
    cur[top++]=x;
    return root;
}
node * findroot(node * x)
{
    top=0;
    node * t=dfs(x);
    int i;
    for (i=0;i<top-2;i+=2)
    {
        cur[i]=join(cur[i],cur[i+1]);
    }
    int j=i;
    for (j-=2;j>=0;j-=2)
    {
        t=join(t,cur[j]);
    }
    for (;i<top;i++)
    {
        t=join(t,cur[i]);
    }
    return t;
}
int father[300005];
int findroots(int x)
{
    int root;
    for (root=x;father[root]!=-1;root=father[root]);
    int temp;
    for (;father[x]!=-1;)
    {
        temp=father[x];
        father[x]=root;
        x=temp;
    }
    return root;
}
void uni(int x,int y)
{
    x=findroots(x);
    y=findroots(y);
    father[x]=y;
}
int queries(node * x)
{
    node * t=findroot(x);
    if (t==x) return t->val;
    return t->tag+x->val;
}
void reset(node * y,int w,int flag=0)
{
    node * t=findroot(y);
    if (t==y)
    {
        y->ch->left=null;
        y->ch->val+=y->tag;
        y->ch->tag+=y->tag;
        node * t=u(y->ch);
        y->ch=null;
        if (flag==0) y->val+=w; else y->val=w;
        root=join(t,y);
        return;
    }
    t->ch=y->right;
    y->right->tag+=y->tag;
    y->right->val+=y->tag;
    y->right->left=t;
    y->tag+=t->tag;
    y->left=null;
    y->right=null;
    y->ch->tag+=y->tag;
    y->ch->val+=y->tag;
    y->ch->left=null;
    node * z=u(y->ch);
    if (flag==0) y->val+=w; else y->val=w;
    y->ch=null;
    root=join(join(y,z),t);
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    null=new_node();
    null->left=null;
    null->right=null;
    null->ch=null;
    int n;
    scanf("%d",&n);
    int i;
    int sum_tag=0;
    for (i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        a[i]=new_node(x);
        b[i]=new_node(x);
        if (i==0) root=b[i]; else root=join(root,b[i]);
        father[i]=-1;
    }
    int m;
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        static char c[15];
        scanf("%s",c);
        if (c[0]=='F')
        {
            if (c[1]=='1')
            {
                int x;
                scanf("%d",&x);
                if (c[2]=='*') printf("    * F1 %d = ",x);
                x--;
                printf("%d\n",queries(a[x])+sum_tag);
            }
            else if (c[1]=='2')
            {
                int x;
                scanf("%d",&x);
                if (c[2]=='*') printf("    * F2 %d = ",x);
                x--;
                printf("%d\n",findroot(a[x])->val+sum_tag);
            }
            else if (c[1]=='3')
            {
                printf("%d\n",root->val+sum_tag);
            }
        }
        else if (c[0]=='A')
        {
            if (c[1]=='1')
            {
                int x;
                scanf("%d",&x);
                x--;
                int w;
                scanf("%d",&w);
                node * t;
                t=findroot(a[x]);
                node * y=a[x];
                if (t==y)
                {
                    y->ch->left=null;
                    y->ch->val+=y->tag;
                    y->ch->tag+=y->tag;
                    node * t=u(y->ch);
                    y->ch=null;
                    y->val+=w;
                    join(t,y);
                    reset(b[findroots(x)],findroot(a[x])->val,1);
                    continue;
                }
                t->ch=y->right;
                y->right->tag+=y->tag;
                y->right->val+=y->tag;
                y->right->left=t;
                y->val+=t->tag;
                y->tag+=t->tag;
                y->left=null;
                y->right=null;
                y->ch->tag+=y->tag;
                y->ch->val+=y->tag;
                y->ch->left=null;
                y->val+=w;
                node * z=u(y->ch);
                y->ch=null;
                join(join(y,z),t);
                reset(b[findroots(x)],findroot(a[x])->val,1);
            }
            else if (c[1]=='2')
            {
                int x;
                scanf("%d",&x);
                x--;
                node * t=findroot(a[x]);
                int w;
                scanf("%d",&w);
                t->tag+=w;
                t->val+=w;
                reset(b[findroots(x)],w);
            }
            else if (c[1]=='3')
            {
                int x;
                scanf("%d",&x);
                sum_tag+=x;
            }
        }
        else if (c[0]=='U')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            if (findroots(x)==findroots(y)) continue;
            reset(b[findroots(x)],-999999999,1);
            reset(b[findroots(y)],-999999999,1);
            join(findroot(a[x]),findroot(a[y]));
            findroot(b[x]);
            uni(x,y);
            reset(b[findroots(y)],findroot(a[x])->val,1);
        }
    }
    return 0;
}