【bzoj2759】一个动态树好题

2015.06.11 19:01 Thu | 33次阅读 | 旧日oi | 固定链接 | 源码

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]

题解

膜fhq……
观察可以发现,如果把每个p[i]设为i的父亲节点的话,我们可以把这些东西变成一个基环森林,每个点存一个k和一个b,一个数到达这个点时要经过什么变换能得到答案。对于每个环,我们可以特殊处理一条边,把一个节点设为根,另一个节点变成根的special father,把它拎出去,然后剩下的就可以用lct来维护了。
查询的时候先找到当前的树根root,然后把root的specialfather access+splay一下,维护出这时的k和b是多少,然后就有k*x[root]+b=x[root],用exgcd解一下方程,求出x[root],然后再把询问的点access+splay,把x[root]带进去就行了。
修改比较麻烦,设修改点x所在树的根节点是root,若x=root,则直接把special father断掉,否则判断点x是否在环上,方法:access+splay点x,断掉左节点,查询当前root的special father所在的根,如果根不是root,说明x在环里,这样的话把root的special father变成正常的father。
接下来连新的边,access+splay(x)之后,如果新的点p的树根等于x,说明又形成了环,把x的sfa设为p,否则把fa设为p。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 10007
#define N 30005
#define is(x) (son[fa[x]][1]==x)
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define ls son[x][0]
#define rs son[x][1]
struct Equal
{
    int k,b;
    int f(int x){return (k*x+b)%mod;}
    Equal operator + (const Equal &y)const
    {
        Equal re;
        re.k=k*y.k%mod;
        re.b=(b*y.k+y.b)%mod;
        return re;
    }
}sum[N],num[N];
int n,q;
int son[N][2],fa[N],sfa[N];
int vis[N],dfn;
void dfs(int u)
{
    vis[u]=dfn;
    if(vis[fa[u]]==dfn)
    {
        sfa[u]=fa[u];
        fa[u]=0;
        return;
    }
    if(!vis[fa[u]]) dfs(fa[u]);
}
void exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);y-=a/b*x;
}
int inv(int k)
{
    int x,y;
    exgcd((k+mod)%mod,mod,x,y);
    return (x%mod+mod)%mod;
}
void pushup(int x)
{
    sum[x]=sum[ls]+num[x]+sum[rs];
}
void link(int x,int y,int d)
{
    fa[x]=y;son[y][d]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
    if(isroot(y)) fa[x]=z;else link(x,z,is(y));
    link(t,y,id);link(y,x,!id);
    son[0][0]=son[0][1]=fa[0]=0;
    pushup(y);
}
void splay(int x)
{
    int y,z;
    while(!isroot(x))
    {
        y=fa[x],z=fa[y];
        if(isroot(y))
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
    pushup(x);
}
void access(int x)
{
    int p=0;
    while(x)
    {
        splay(x);
        rs=p;pushup(x);
        p=x;x=fa[x];
    }
}
void movetoroot(int x)
{
    access(x);splay(x);
}
int find(int x)
{
    movetoroot(x);
    while(ls) x=ls;
    return x;
}
int query(int x)
{
    int rt=find(x);
    movetoroot(sfa[rt]);
    int k=sum[sfa[rt]].k,b=sum[sfa[rt]].b;
    if(k==1) return b?-1:-2;
    int temp=(mod-b)*inv(k-1)%mod;
    movetoroot(x);
    return sum[x].f(temp);
}
void change(int x,int k,int p,int b)
{
    int rt=find(x);
    num[x].k=k;num[x].b=b;pushup(x);
    if(rt==x) sfa[x]=0;
    else
    {
        movetoroot(x);
        fa[ls]=0;ls=0;pushup(x);
        if(find(sfa[rt])!=rt)
        {
            movetoroot(rt);
            fa[rt]=sfa[rt];
            sfa[rt]=0;
        }
    }
    movetoroot(x);
    if(find(p)==x) sfa[x]=p;
    else fa[x]=p;
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>n;
    for(int k,p,b,i=1;i<=n;i++)
    {
        scanf("%d%d%d",&k,&p,&b);
        num[i].k=sum[i].k=k%mod;
        num[i].b=sum[i].b=b%mod;
        fa[i]=p;
    }
    for(int i=1;i<=n;i++) if(!vis[i]) dfn++,dfs(i);
    cin>>q;char s[2];
    sum[0].k=1;
    for(int x,k,p,b,i=1;i<=q;i++)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='A') printf("%d\n",query(x));
        else scanf("%d%d%d",&k,&p,&b),change(x,k,p,b);
    }
    return 0;
}
至此,三天的大数据结构专题训练已经差不多结束,感觉自己的代码能力的确有所提高,下一阶段的目标,字符串!```