一个动态树好题

wjh15101051's space

卧薪尝胆，厚积薄发。

一个动态树好题

Date: Thu Jan 17 18:53:40 CST 2019

In Category: NoCategory

Description：

$n$ 个同余方程： $x_i\equiv k_i\times xp_i+b_i(\text{mod }10007)$ 。 $m$ 个操作：修改某个不等式的 $k_i,p_i,b_i$ ，查询某个变量的值。

$1\leqslant n\leqslant 30000$

Solution：

首先按照依赖关系可以建成基环树森林，那么求解答案我们只要把环上的方程依次代入就可以把答案解出来，然后再处理非环上的部分就可以了，然后还要修改，由题目可以想到使用 $LCT$ 维护基环树，说起来很简单，代码是抄的。

注意在刚开始要找到环然后处理特殊指针。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

#define MAXN 30010

#define MOD 10007

int n,m;

struct data

{

	int k,b;

	data(){}

	data(int k_,int b_){k = k_;b = b_;}

	friend data operator + (data x,data y)

	{

		return data(x.k * y.k % MOD,(x.b * y.k % MOD + y.b) % MOD);

	}

};

#define I inline

struct node

{

	int c[2],fa;

	int sp;

	data sum,val;

}t[MAXN];

I bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

I int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

I void maintain(int rt)

{

	t[rt].sum = t[rt].val;

	if(t[rt].c[0])t[rt].sum = t[t[rt].c[0]].sum + t[rt].sum;

	if(t[rt].c[1])t[rt].sum = t[rt].sum + t[t[rt].c[1]].sum;

	return;

}

I void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

#define R register

I void rotate(int x)

{

	R int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

I void splay(int x)

{

	while(!isroot(x))

	{

		R int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

I void access(int k){for(R int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

I int findroot(int k){access(k);splay(k);while(t[k].c[0])k = t[k].c[0];return k;}

I void cut(int k){access(k);splay(k);t[t[k].c[0]].fa = 0;t[k].c[0] = 0;maintain(k);return;}

int inv[MOD];

I void query(int k)

{

	R data tmp1,tmp2;

	access(k);splay(k);

	tmp1 = t[k].sum;

	R int rt = findroot(k);

	access(t[rt].sp);splay(t[rt].sp);

	tmp2 = t[t[rt].sp].sum;

	if(tmp2.k == 1)

	{

		if(tmp2.b == 0)puts("-2");

		else puts("-1");

	}

	else

	{

		R int valrt = inv[(1 - tmp2.k + MOD) % MOD] * tmp2.b % MOD;

		printf("%d\n",(tmp1.k * valrt % MOD + tmp1.b) % MOD);

	}

	return;

}

I bool incir(int x,int y)

{

	access(t[y].sp);

	splay(t[y].sp);

	splay(x);

	return (x == t[y].sp || (!isroot(t[y].sp)));

}

I void change(int x,int k,int p,int b)

{

	access(x);splay(x);

	t[x].val.k = k;t[x].val.b = b;

	maintain(x);

	R int rt = findroot(x);

	if(rt == x)

	{

		if(findroot(p) == rt)t[x].sp = p;

		else t[rt].sp = 0,t[rt].fa = p;

	}

	else

	{

		if(incir(x,rt))

		{

			cut(x);

			splay(rt);

			t[rt].fa = t[rt].sp;

			t[rt].sp = 0;

		}

		else cut(x);

		if(findroot(p) == x)t[x].sp = p;

		else t[x].sp = 0,t[x].fa = p;

	}

	return;

}

int nxt[MAXN];

int vis[MAXN],cnt = 0;

void prework(int k)

{

	vis[k] = cnt;

	if(vis[nxt[k]] == cnt)

	{

		t[k].fa = 0;

		t[k].sp = nxt[k];

		return;

	}

	else t[k].fa = nxt[k];

	prework(nxt[k]);

	return;

}

char getc()

{

	R char c = getchar();

	while(!isalpha(c))c = getchar();

	return c;

}

int main()

{

	inv[1] = 1;

	for(R int i = 2;i < MOD;++i)inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

	n = rd();

	for(R int i = 1;i <= n;++i)

	{

		t[i].val.k = rd();nxt[i] = rd();t[i].val.b = rd();

	}

	for(R int i = 1;i <= n;++i)

	{

		if(!vis[i])++cnt,prework(i);

	}

	scanf("%d",&m);

	R char opt;

	R int x,k,p,b;

	for(R int i = 1;i <= m;++i)

	{

		opt = getc();

		if(opt == 'A')

		{

			x = rd();

			query(x);

		}

		else

		{

			x = rd();k = rd();p = rd();b = rd();

			change(x,k,p,b);

		}

	}

	return 0;

}

In tag: 数据结构-LCT

wjh15101051