BZOJ 1455 로마 게임 누드

제목:링크

방법: 병합 가능

해결:

2중에 온 며칠 동안 잊어버리고 강의를 병행하여 누드 문제를 찾아서 긁었다.

결합 작업의 경우 하나가 비어 있으면 루트가 다른 것입니다.

그리고 우리는 x 키 값이 y보다 작다고 가정해도 무방하다.

그러면 왼쪽 편수 의 좌우 자수 가 모두 왼쪽 편수 이기 때문에 전체 과정 은 귀속 을 이루었다

즉 x의 오른쪽 나무를 Y가 뿌리인 나무와 합친다.

합병 후 왼쪽 편향을 유지하면 NPL의 왼쪽이 오른쪽보다 크다는 것을 보증합니다.

나중에 루트 노드의 NPL을 업데이트합니다.

사실 이상은 합병의 전 과정이며, 단지 기억을 깊이 있게 서술할 뿐이다.

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1000010
using namespace std;
int ch[N][2],h[N],key[N],fa[N];
bool col[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
    if(!x)return y;
    if(!y)return x;
    if(key[y]<key[x])swap(x,y);
    ch[x][1]=merge(ch[x][1],y);
    if(h[ch[x][1]]>h[ch[x][0]])swap(ch[x][0],ch[x][1]);
    if(!h[ch[x][1]])h[x]=0;
    else h[x]=h[ch[x][1]]+1;
    return x;
}
int n,q;
char s[5];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&key[i]);
    for(int i=1;i<=n;i++)fa[i]=i;
    h[0]=-1;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",s);
        if(s[0]=='M')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(col[x]||col[y])continue;
            int fx=find(x),fy=find(y);
            if(fx!=fy)
            {
                int t=merge(fx,fy);
                fa[fx]=t,fa[fy]=t;
            }
        }else
        {
            int x;
            scanf("%d",&x);
            if(col[x])printf("%d
",0);
            else
            {   
                int fx=find(x);
                col[fx]=1;
                printf("%d
",key[fx]);
                fa[fx]=merge(ch[fx][0],ch[fx][1]);
                fa[fa[fx]]=fa[fx];
            }
        }
    }
}