bzoj2759:一个动态树好题 (LCT+Exgcd)
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2759
题目分析:这是一道真动态树好题,不像某些其它自称好题的题目(bzoj4300“绝世好题”,其实是大水题)。
言归正传,我们来看看这道题。如果有一条方程是a=ka+b%10007的形式,且0<=a<10007,你会解a吗?很明显,当k=0时,a=b;当k=1时,若b=0,则有无穷多解,否则无解;当k>1时,用扩展欧几里得解。那么假设有两条方程:a1=k1a2+b1%10007,a2=k2a1+b2%10007,你会解a1吗?很简单,我们把前面式子的a2用后面的式子代替,然后就和刚才的一样了。而且这些式子是可以用splay进行信息合并的。
现在题目给出了很多条形如a_i=ki*a_pi+bi%10007的式子,我们认为i的父亲是pi,这样我们就得到了一棵环套树森林,然后我们任意选择一个环上的点i,将i到pi的边断掉,就变成了一个普通的森林,并且我们开一个域special_fa,令Node[i]->special_fa=pi,记录下来:
图中的实边代表树上的边,虚边代表special_fa边。很明显只有一棵树的根,special_fa才会有值。当我们要求a的值的时候,先找到它的根root,然后Access(Node[root]->special_fa),求出Node[root]->special_fa的值,再求出root的值,再通过Access(a),求出a的值。
现在的问题在于修改操作,假设我要改变a的父亲为p,又该怎么做呢?我们先看一下a是否为某棵树的根,是的话就断掉a的special_fa边,然后看一下p是否在a的子树中,是的话a的special_fa变为p,否则a的path_parent变为p;若a不是某棵树的根,先断掉a和它原父亲的边,然后看p是否在a的子树……(同上),最后如果a在原先的环上,还要令a的原根的special_fa边变为path_parent边。(看看上图就可以自己脑补一下了)
擅长数据结构的我这题都调了两个小时(说实话我敲LCT基本上是敲完立马过样例,一交立马AC那种),主要是有些细节一开始没有想清楚,还有码code的时候状态不是很好,出现各种错误。比如说splay信息的合并一开始搞错了;”if (F->fa)”写成了while;我在解扩展gcd的时候,为了避免负数让程序去解Exgcd(M,k-1)而不是1-k,结果最后Y忘了取反;没有判断a是根的情况;修改了k和b的值没有重新再Up()一次;给某个点打path_parent标记之前没有将它Splay等等……QAQ
CODE:
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=30010;
const int M=10007;
struct Tnode
{
int vk,vb,K,B,path_parent,special_fa;
Tnode *fa,*son[2];
int Get_d() { return fa->son[1]==this; }
void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
void Up()
{
K=vk,B=vb;
if (son[0]) B=(K*son[0]->B+B)%M,K=K*son[0]->K%M;
if (son[1]) B=(son[1]->K*B+son[1]->B)%M,K=son[1]->K*K%M;
}
} tree[maxn];
Tnode *Node[maxn];
int cur=-1;
int X,Y;
int n,q;
Tnode *New_node()
{
cur++;
tree[cur].vk=tree[cur].K=0;
tree[cur].vb=tree[cur].B=0;
tree[cur].path_parent=tree[cur].special_fa=0;
tree[cur].fa=tree[cur].son[0]=tree[cur].son[1]=NULL;
return tree+cur;
}
void Zig(Tnode *P)
{
int d=P->Get_d();
Tnode *F=P->fa;
if (P->son[!d]) F->Connect(P->son[!d],d);
else F->son[d]=NULL;
if (F->fa) F->fa->Connect(P, F->Get_d() );
else P->fa=NULL;
F->Up();
P->Connect(F,!d);
P->path_parent=F->path_parent;
F->path_parent=0;
}
void Splay(Tnode *P)
{
while (P->fa)
{
Tnode *F=P->fa;
if (F->fa) ( P->Get_d()^F->Get_d() )? Zig(P):Zig(F);
Zig(P);
}
P->Up();
}
void Down(int x)
{
Splay(Node[x]);
Tnode *&tag=Node[x]->son[1];
if (tag)
{
tag->fa=NULL;
tag->path_parent=x;
tag=NULL;
Node[x]->Up();
}
}
void Access(int x)
{
Down(x);
int y=Node[x]->path_parent;
while (y)
{
Down(y);
Node[y]->Connect(Node[x],1);
Node[y]->Up();
Node[x]->path_parent=0;
x=y;
y=Node[x]->path_parent;
}
}
Tnode *Find_root(Tnode *P)
{
if (!P->son[0]) return P;
return Find_root(P->son[0]);
}
bool Judge(Tnode *P,int y)
{
Access(y);
Splay(Node[y]);
return Find_root(Node[y])==P;
}
void Link(int x,int y)
{
Splay(Node[y]);
Node[y]->path_parent=x;
}
void Exgcd(int a,int b)
{
if (!b)
{
X=1,Y=0;
return;
}
Exgcd(b,a%b);
int u=Y;
Y=X-u*(a/b);
X=u;
}
int Solve(int k,int b)
{
k--;
Exgcd(M,k);
Y*=b;
Y=-Y;
Y=(Y%M+M)%M;
return Y;
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&n);
for (int i=1; i<=n; i++) Node[i]=New_node();
for (int i=1; i<=n; i++)
{
int k,p,b;
scanf("%d%d%d",&k,&p,&b);
Node[i]->vk=k;
Node[i]->vb=b;
Node[i]->Up();
if ( !Judge(Node[i],p) ) Link(p,i);
else Node[i]->special_fa=p;
}
scanf("%d",&q);
while (q--)
{
char c=getchar();
while ( c!='A' && c!='C' ) c=getchar();
if (c=='A')
{
int a;
scanf("%d",&a);
Access(a);
Splay(Node[a]);
Tnode *P=Find_root(Node[a]);
int sfa=P->special_fa;
Access(sfa);
Splay(P);
int k=P->K;
int b=P->B;
int root;
if (!k) root=b;
if (k==1)
{
if (b) printf("-1\n");
else printf("-2\n");
continue;
}
if (k>1) root=Solve(k,b);
root=(P->vk*root+P->vb)%M;
if (P==Node[a])
{
printf("%d\n",root);
continue;
}
Access(a);
Splay(P);
k=P->son[1]->K;
b=P->son[1]->B;
root=(k*root+b)%M;
printf("%d\n",root);
}
if (c=='C')
{
int a,k,p,b;
scanf("%d%d%d%d",&a,&k,&p,&b);
Access(a);
Splay(Node[a]);
Tnode *P=Find_root(Node[a]);
if (Node[a]==P)
{
P->special_fa=0;
P->vk=k;
P->vb=b;
P->Up();
Access(p);
Splay(Node[p]);
if ( Find_root(Node[p])==P ) P->special_fa=p;
else P->path_parent=p;
continue;
}
Access(P->special_fa);
Splay(Node[a]);
bool flag=(Find_root(Node[a])==P);
Access(a);
Splay(Node[a]);
Node[a]->son[0]->fa=NULL;
Node[a]->son[0]->path_parent=Node[a]->path_parent;
Node[a]->path_parent=0;
Node[a]->son[0]=NULL;
Node[a]->vk=k;
Node[a]->vb=b;
Node[a]->Up();
if ( Judge(Node[a],p) ) Node[a]->special_fa=p;
else Node[a]->path_parent=p;
if ( flag && !Judge(P,p) )
{
Splay(P);
P->path_parent=P->special_fa;
P->special_fa=0;
}
}
}
return 0;
}
上一篇: Savage(扩展欧几里得)
下一篇: 微信小程序的学习(1)