JZOJ5822. 【NOIP提高A组模拟2018.8.16】 量子纠缠

题目大意

给定一个集合，支持加入，纠缠操作，并查询某个字符串是否在集合里面。

题解

先不看纠缠操作，很显然一棵trie就可以解决。
考虑纠缠操作，其实就是将trie树上面的某些节点进行合并，
用并查集来合并。
设需要纠缠的两个串a,b在tire上的最后一个节点分别为x,y，
设过程entanglement(x,y)表示将x跟y纠缠并把y的信息合并到x上面，
从0到9枚举儿子，
如果x,y都有这个儿子，就entanglement(x的儿子,y的儿子)，
如果x没有这个儿子，而y有，就将x的这个儿子指向y的这个儿子

code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#define ll long long
#define N 8000003
#define M 103
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

int f[N],son[N][10],g[N],m,cz,x,y,t,tot;

int get(int x){return f[x]=(x==f[x]?x:get(f[x]));}

void entanglement(int x,int y) 
{
    if(x==y)return;
    f[y=get(y)]=x=get(x);
    g[x]+=g[y];
    for(int i=0;i<10;i++)
    {
        if(son[x][i] && son[y][i])entanglement(son[x][i],son[y][i]);else
        if(!son[x][i] && son[y][i])son[x][i]=son[y][i];
        x=get(x);
    }
}

int main()
{
    freopen("quantum.in","r",stdin);
    freopen("quantum.out","w",stdout);

    for(f[1]=1,read(m),tot=1;m;m--)
    {
        read(cz);
        if(cz==1)
        {
            for(ch=G();ch<'0' || ch>'9';ch=G());
            for(x=1;'0'<=ch && ch<='9';ch=G())
            {
                x=get(x);t=ch-'0';
                if(!son[x][t])son[x][t]=++tot,f[tot]=tot;
                x=son[x][t];
            }
            g[get(x)]++;
        }
        else
        if(cz==2)
        {
            for(ch=G();ch<'0' || ch>'9';ch=G());
            for(x=1;'0'<=ch && ch<='9';ch=G())
            {
                x=get(x);t=ch-'0';
                x=son[x][t];
            }
            P(g[get(x)]?'1':'0');P('\n');
        }
        else
        {
            for(ch=G();ch<'0' || ch>'9';ch=G());
            for(x=1;'0'<=ch && ch<='9';ch=G())
            {
                x=get(x);t=ch-'0';
                if(!son[x][t])son[x][t]=++tot,f[tot]=tot;
                x=son[x][t];
            }

            for(ch=G();ch<'0' || ch>'9';ch=G());
            for(y=1;'0'<=ch && ch<='9';ch=G())
            {
                y=get(y);t=ch-'0';
                if(!son[y][t])son[y][t]=++tot,f[tot]=tot;
                y=son[y][t];
            }

            entanglement(x,y);
        }
    }

    return 0;
}