代码

#include <cstdio>
#include <cstring>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
#define g(x, y, z) for(int x = (y); x < (z); ++x)
#define h(x, y, z) for(int x = (y); x >= (z); --x)
using namespace std;

const int MAXN = 200000 + 7;
const int MAXK = 50 + 3;
const int MAXSL = 10000000 + 7;
const int MOD = 998244353;
const int MAXDEL = 1000 + 7;

const int MAXNODE = MAXN * MAXK + MAXDEL * MAXK * MAXK / 2 + 7;

#define ensure(x) ensureImpl(x, __LINE__, #x)
void ensureImpl(bool x, int line, const char *info)
{
	return;
	if(!x)
	{
		printf("failed on line %d: %s\n", line, info);
	}
}
	
struct IO
{
	char inBuf[1 << 25], outBuf[1 << 25];
	char *inPos, *outPos;
	IO()
	{
		fread(inBuf, sizeof(*inBuf), sizeof(inBuf), stdin);
		inPos = inBuf; outPos = outBuf;
	}
	~IO()
	{
		fwrite(outBuf, sizeof(*outBuf), outPos - outBuf, stdout);
	}
	IO &operator <<(char x)
	{
		*outPos++ = x;
		return *this;
	}
	IO &operator >>(char &c)
	{
		c = *inPos++;
		return *this;
	}
	IO &operator <<(int x)
	{
		if(!x)
			return *this << '0';
		if(x < 0)
		{
			x = -x;
			*this << '-';
		}
		char buf[10];
		char *pos = buf + sizeof(buf);
		while(x)
		{
			*--pos = '0' + (char) (x % 10);
			x /= 10;
		}
		int len = buf + sizeof(buf) - pos;
		memcpy(outPos, pos, len);
		outPos += len;
		return *this;
	}
	IO &operator >>(int &x)
	{
		// TODO: negative number
		x = 0;
		char c; *this >> c;
		while(c < '0' || c > '9')
			*this >> c;
		while(c >= '0' && c <= '9')
		{
			x = (x << 3) + (x << 1) + (c - '0');
			*this >> c;
		}
		return *this;
	}
	char *getStr()
	{
		char *ret = ++inPos;
		while(*inPos != ' ')
			++inPos;
		*inPos++ = 0;
		return ret;
	}
	void getVisible(char &c)
	{
		*this >> c;
		while(c < (char) 33 || c > (char) 126)
			*this >> c;
	}
} io;

struct Link
{
	int ls, rs, c;
} l[MAXN];

struct Node
{
	int son[6], cnt, go;
} e[MAXNODE];
int ntop = 1;

int newNode(int fa, int x)
{
	ensure(ntop < MAXNODE);
	int g = ntop++;
	if(fa)
	{
		int &c = e[e[fa].go].son[x];
		if(!c)
			c = newNode(e[fa].go, x);
		e[g].go = c;
	}
	return g;
}

void insertSingle(int c)
{
	int &s = e[0].son[c];
	if(!s)
		s = newNode(0, c);
	++e[s].cnt;
}

int query(const char *a, int k)
{
	int ok = k;
	int c = 0;
	while(--k)
	{
		// printf("MEET %d\n", *a - '1');
		if(!(c = e[c].son[*a++ - '1']))
			return 0;
	}
	int ans = 1;
	while(*a)
	{
		// printf("MEET %d\n", *a - '1');
		if(!(c = e[c].son[*a++ - '1']))
			return 0;
		// printf(" CNT %d | %d\n", e[c].cnt, c);
		ans = (long long) ans * e[c].cnt % MOD;
		c = e[c].go;
		ensure(c || ok == 1);
	}
	return ans;
}

void opr(int x, int y)
{
	bool join;
	if(y)
	{
		join = true;
		ensure(!l[x].rs);
		ensure(!l[y].ls);
		// ensure(x and y not together);
		l[x].rs = y;
		l[y].ls = x;
	}
	else
	{
		join = false;
		y = l[x].rs;
		ensure(y);
	}
	
	int lef = x;
	for(int i = 2; l[lef].ls && i < MAXK; ++i)
		lef = l[lef].ls;
	int c = e[0].son[l[lef].c], lxc = 0, lxi = 0;
	ensure(c);
	
	for(;;)
	{
		int i, t;
		if(lxc)
		{
			i = lxi--;
			t = y;
			c = lxc = e[lxc].go;
			ensure(c);
		}
		else
		{
			i = 1;
			t = l[lef].rs;
			if(lef == x)
				lxc = c;
		}
		for(; t && i < MAXK; ++i)
		{
			// printf("i %d, t %d, c %d\n", i, t, c);
			if(!e[c].son[l[t].c])
			{
				if(!lxc || !join)
					ensure(0);
				e[c].son[l[t].c] = newNode(c, l[t].c);
			}
			c = e[c].son[l[t].c];
			if(lxc)
			{
				// printf("+CNT %d\n", c);
				// static long long cnt = 0;
				// if(++cnt % 1000000 == 0)
					// fprintf(stderr, "cnt = %d\n", cnt);
				if(join)
					++e[c].cnt;
				else
					--e[c].cnt;
			}
			if(t == x)
			{
				lxc = c;
				lxi = i;
			}
			t = l[t].rs;
		}
		if(lef == x)
			break;
		else
			lef = l[lef].rs;
	}
	
	if(!join)
	{
		l[x].rs = 0;
		l[y].ls = 0;
	}
}

int main()
{
	int n, m; io >> n >> m;
	f(i, 1, n)
	{
		io >> l[i].c;
		--l[i].c;
		insertSingle(l[i].c);
	}
	while(m--)
	{
		char op; io.getVisible(op);
		if(op == '1')
		{
			int x, y; io >> x >> y;
			opr(x, y);
			// printf("==========================\n");
			// g(i, 0, ntop)
			// {
				// printf("NODE %d\n\tcnt %d, go %d, son:", i, e[i].cnt, e[i].go);
				// g(j, 0, 6) printf(" %d", e[i].son[j]);
				// printf("\n");
			// }
			// printf("==========================\n");
		}
		else if(op == '2')
		{
			int x; io >> x;
			opr(x, 0);
		}
		else
		{
			char *s = io.getStr();
			int k; io >> k;
			io << query(s, k) << '\n';
		}
	}
	return 0;
}

评测结果