Findstrなのです

lk砍树的板，记下来好了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#define PROC "2049"
using namespace std;
const int maxn=10100;
struct hja{
    hja *fa, *ch[2];
    bool tag;
     
    void gettag()
    {
        tag^=1;
    }
     
    void pushdown()
    {
        if (tag)
        {
            ch[1]->gettag();
            ch[0]->gettag();
            swap(ch[0],ch[1]);
            tag=0;
        }
    }
} rnil;
hja *nil=&rnil;
int n, m;
namespace LCT{
    hja tree[maxn];
    void init(hja &now)
    {
        now.ch[0]=now.ch[1]=now.fa=nil;
    }
    void init()
    {
        for (int i=1; i<=n; i++)
            init(tree[i]);
    }
    bool isRoot(hja *now)
    {
        return now->fa->ch[0]!=now&&now->fa->ch[1]!=now;
    }
    void rotate(hja *now)
    {
        hja *fa=now->fa;
        hja *gfa=fa->fa;
        bool d=fa->ch[1]==now;
        if (!isRoot(fa))
            gfa->ch[gfa->ch[1]==fa]=now;
        now->fa=gfa;
        fa->fa=now;
        fa->ch[d]=now->ch[d^1];
        now->ch[d^1]->fa=fa;
        now->ch[d^1]=fa;
    }
    stack<hja*> sta;
    void splay(hja *now)
    {
        hja *pre=now;
        sta.push(pre);
        while (!isRoot(pre))
        {
            pre=pre->fa;
            sta.push(pre);
        }
        while (!sta.empty())
        {
            sta.top()->pushdown();
            sta.pop();
        }
        while (!isRoot(now))
        {
            hja *fa=now->fa, *gfa=now->fa->fa;
            if (!isRoot(fa))
            {
                if ((gfa->ch[1]==fa)!=(fa->ch[1]==now))
                    rotate(now);
                else
                    rotate(fa);
            }
            rotate(now);
        }
    }
    void access(hja* nowp)
    {
        for (hja *son=nil; nowp!=nil; nowp=nowp->fa)
        {
            splay(nowp);
            nowp->ch[1]=son;
            son=nowp;
        }
    }
    void access(int nowp)
    {
        access(&tree[nowp]);
    }
 
    void makeRoot(hja* nowp)
    {
        access(nowp);
        splay(nowp);
        nowp->gettag();
    }
    void makeRoot(int nowp)
    {
        makeRoot(&tree[nowp]);
    }
    void cut(hja* p1, hja* p2)
    {
        makeRoot(p1);
        access(p2);
        splay(p2);
        p1->fa=nil;
        p2->ch[0]=nil;
    }
    void cut(int p1, int p2)
    {
        cut(&tree[p1],&tree[p2]);
    }
    hja* find(hja *p1)
    {
        access(p1);
        splay(p1);
        while (p1->ch[0]!=nil)
            p1=p1->ch[0];
        return p1;
    }
    int find(int nowp)
    {
        return find(&tree[nowp])-tree;
    }
    bool find(int p1, int p2)
    {
        return find(p1)==find(p2);
    }
    bool find(hja* p1, hja* p2)
    {
        return find(p1)==find(p2);
    }
    void link(hja* p1, hja* p2)
    {
        makeRoot(p1);
        p1->fa=p2;
        access(p1);
    }
    void link(int p1, int p2)
    {
        link(&tree[p1],&tree[p2]);
    }
}
 
char s[10];
 
int main()
{
#ifdef YJQ_LOCAL
    freopen(PROC".in","r",stdin);
//  freopen(PROC".out","w",stdout);
#endif
    int tmp1,tmp2,tmp3;
    scanf("%d%d",&n,&m);
    LCT::init();
    while(m--)
    {
        scanf("%s%d%d",s+1,&tmp1,&tmp2);
        if (s[1]=='Q')
            puts(LCT::find(tmp1,tmp2)?"Yes":"No");
        if (s[1]=='C')
            LCT::link(tmp1,tmp2);
        if (s[1]=='D')
            LCT::cut(tmp1,tmp2);
    }
    fclose(stdout);
    return 0;
}

sro YJQ orz

#include<cstdio>
#include<cstring>
const int maxm=26, maxn=101000;

struct node{
	int par, val;
	int go[maxm];
};
node sam[maxn*2];
int sn;
int root,last;
char read[maxn];
int number[maxn];

struct yjq{
	int f, t, n;
};
yjq naive[maxn<<2];
int nn, pre[maxn<<1], fst[maxn<<1];

bool end[maxn<<1];

void addedge(int f, int t)
{
	nn++;
	naive[nn].f=f;
	naive[nn].t=t;
	if (fst[f])	
		naive[pre[f]].n=nn;
	else
		fst[f]=nn;
	pre[f]=nn;
}

void extend(int now)
{
	sn++;
	sam[sn].val=sam[last].val+1;
	int p=last;
	int np=sn;
	for (; p&&(!sam[p].go[now]); p=sam[p].par)
		sam[p].go[now]=np;
	if (!p)
		sam[np].par=root;
	else
	{
		int q=sam[p].go[now];
		if (sam[q].val==sam[p].val+1)
			sam[np].par=q;
		else
		{
			int nq=++sn;
			sam[nq].val=sam[p].val+1;
			memcpy(sam[nq].go,sam[q].go,sizeof sam[q].go);
			sam[nq].par=sam[q].par;
			sam[q].par=nq;
			sam[np].par=nq;
			for (; p&&sam[p].go[now]==q; p=sam[p].par)
			{
				sam[p].go[now]=nq;
			}
		}
	}
	last=np;
}

void walk_sam(int nowp)
{
	for (int c=0; c<maxm; c++)
	{
		if (sam[nowp].go[c])
		{
			printf("%d --%c-> %d\n",nowp,c+'a',sam[nowp].go[c]);
		}
	}
}

int main()
{
	scanf("%s",read+1);
	int n=strlen(read+1);
	root=last=1;
	sn=1;
	for (int i=1; i<=n; i++)
	{
		number[i]=read[i]-'a';
		extend(number[i]);
	}
	for (int i=root; i<=sn; i++)
		addedge(sam[i].par,i);
	dfs(root);
	return 0;
}