BZOJ2759: 一个动态树好题

BZOJ2759: 一个动态树好题

Description

有N个未知数x[1..n]和N个等式组成的同余方程组:
x[i]=k[i]*x[p[i]]+b[i] mod 10007
其中,k[i],b[i],x[i]∈[0,10007)∩Z
你要应付Q个事务,每个是两种情况之一:
一.询问当前x[a]的解
A a
无解输出-1
x[a]有多解输出-2
否则输出x[a]
二.修改一个等式
C a k[a] p[a] b[a]

Input

N
下面N行,每行三个整数k[i] p[i] b[i]
Q
下面Q行,每行一个事务,格式见题目描述

Output

对每个询问,输出一行一个整数。
对100%的数据,1≤N≤30000,0≤Q≤100000,时限2秒,其中询问事务约占总数的80%

Sample Input

5
2 2 1
2 3 2
2 4 3
2 5 4
2 3 5
5
A 1
A 2
C 5 3 1 1
A 4
A 5

Sample Output

4276
7141
4256
2126

题解Here!
额,这的确是道$LCT$的好题。。。
好到毒瘤了。。。
题目大意:
给定$n$个形如$x_i=k_i\times x_{p_i}+b_i\mod 10007$的同余方程组,支持修改和询问。
出题人脑洞真大。。。

将每个点$i$的父亲设为$p_i$,我们将会得到一座基环树林。

将环上的一条边拆掉,在边的起始节点新开个域$special_father$记录这条边。($P.S$:好浪费,但是没办法)

于是我们得到了一座森林,显然可以用LCT来维护。

每个节点的权值是个二元组$(k,b)$,记录每个点关于答案的线性关系,合并时左侧代入右侧中。

查询时将$root$的$special\ father$进行$Access+Splay$操作,然后借助这个环通过$exgcd$求出$root.special\ father$的值,然后$Access(x)+Splay(x)$代入出解。

单点查询,没有换根等操作,翻转标记都没有,舒服!

但是那个无解和无穷解怎么整?

我们特判一波:

若环上$k==1$,讨论$b$:

若$b==0$则无穷多解;否则无解

注意$k==0$时要加一些处理,正常求$exgcd$求不出来。

修改的话,因为是单点修改,所以最开始要$Access+Splay$。

修改$x$的父节点时需要讨论:

首先切掉原先的父节点,这个不必多说。

如果$x$是所在树的根 直接切掉$special\ father$就好。

如果$x$不是根,切掉$x$与父节点的联系,然后讨论$x$是否在环上。

设$x$所在树的根节点为$root$。

若$root.special\ father$所在树的根不为$root$,则$x$在环上,将$root$的$special\ father$变为$root$的$fa$节点。

否则切断父节点完毕。

然后讨论新的父节点$p$是否在$x$的子树中

若在,将$x$的$special\ father$设为$p$。

若不在,将$x$的$fa$设为$p$。

然后就是一大堆乱七八糟的细节问题,这个只能看代码了。。。

记得一开始的空节点有值!

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 40010
#define MOD 10007
using namespace std;
int n,m,T=1;
int fa[MAXN],vis[MAXN];
struct node{
int k,b;
node operator +(const node p)const{
node x;
x.k=k*p.k%MOD;
x.b=(b*p.k+p.b)%MOD;
return x;
}
inline int f(int x){return (x*k+b)%MOD;}
};
struct Link_Cut_Tree{
int son[2];
int f,sf;//fa,special_father
node v,sum;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline bool isroot(int rt){
return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt;
}
inline void pushup(int rt){
a[rt].sum=a[a[rt].son[0]].sum+a[rt].v+a[a[rt].son[1]].sum;
}
inline void newnode(int rt,int k,int b){
a[rt].son[0]=a[rt].son[1]=a[rt].f=a[rt].sf=0;
a[rt].v.k=a[rt].sum.k=k;
a[rt].v.b=a[rt].sum.b=b;
}
inline void turn(int rt){
int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;
if(!isroot(x)){
if(a[y].son[0]==x)a[y].son[0]=rt;
else a[y].son[1]=rt;
}
a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;
a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;
pushup(x);pushup(rt);
}
void splay(int rt){
while(!isroot(rt)){
int x=a[rt].f,y=a[x].f;
if(!isroot(x)){
if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);
else turn(x);
}
turn(rt);
}
}
void access(int rt){
for(int i=0;rt;i=rt,rt=a[rt].f){
splay(rt);
a[rt].son[1]=i;
pushup(rt);
}
}
int findroot(int rt){
access(rt);splay(rt);
while(a[rt].son[0])rt=a[rt].son[0];
return rt;
}
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;
return a;
}
int s=exgcd(b,a%b,y,x);
y-=a/b*x;
return s;
}
int inverse(int k){
int x=0,y=0;
int t=exgcd((k+MOD)%MOD,MOD,x,y);
return (x%MOD+MOD)%MOD;
}
void dfs(int rt){
vis[rt]=T;
if(vis[fa[rt]]==T){
a[rt].sf=fa[rt];
return;
}
a[rt].f=fa[rt];
if(!vis[fa[rt]])dfs(fa[rt]);
}
void update(int x,int k,int p,int b){
int rt=findroot(x);
a[x].v.k=k;a[x].v.b=b;
pushup(x);
if(x==rt){
a[x].sf=0;
}
else{
access(x);splay(x);
a[a[x].son[0]].f=0;a[x].son[0]=0;
pushup(x);
if(findroot(a[rt].sf)!=rt){
access(rt);splay(rt);
a[rt].f=a[rt].sf;
a[rt].sf=0;
}
}
access(x);splay(x);
if(findroot(p)==x)a[x].sf=p;
else a[x].f=p;
}
void query(int x){
int rt=findroot(x);
access(a[rt].sf);splay(a[rt].sf);
int k=a[a[rt].sf].sum.k,b=a[a[rt].sf].sum.b;
if(k==1){
if(b==0)printf("-2\n");
else printf("-1\n");
return;
}
int t=(MOD-b)*inverse(k-1)%MOD;
access(x);splay(x);
printf("%d\n",a[x].sum.f(t));
}
void work(){
char ch[2];
int x,k,p,b;
while(m--){
scanf("%s",ch);x=read();
if(ch[0]=='A'){
query(x);
}
else{
k=read();p=read();b=read();
update(x,k,p,b);
}
}
}
void init(){
int k,p,b;
n=read();
newnode(0,1,0);//空节点有值!
for(int i=1;i<=n;i++){
k=read();p=read();b=read();
fa[i]=p;
newnode(i,k,b);
}
m=read();
for(int i=1;i<=n;i++)if(!vis[i]){dfs(i);T++;}
}
int main(){
init();
work();
return 0;
}
上一篇:bzoj 2759一个动态树好题


下一篇:Java SE 8 流库(二)