[UOJ207]共价大爷游长沙(LCT,随机化)

发布于 2018-01-31  84 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[UOJ207]共价大爷游长沙(LCT,随机化)

Description

火车司机出秦川,跳蚤国王下江南,共价大爷游长沙。每个周末,勤劳的共价大爷都会开车游历长沙市。
长沙市的交通线路可以抽象成为一个 n 个点 n−1 条边的无向图,点编号为 1 到 n,任意两点间均存在恰好一条路径,显然两个点之间最多也只会有一条边相连。有一个包含一些点对 (x,y) 的可重集合S,共价大爷的旅行路线是这样确定的:每次他会选择 S 中的某一对点 (x,y),并从 x 出发沿着唯一路径到达 y。
小L是共价大爷的脑残粉,为了见到共价大爷的尊容,小L决定守在这张图的某条边上等待共价大爷的到来。为了保证一定能见到他,显然小L必须选择共价大爷一定会经过的边——也就是所有共价大爷可能选择的路径都经过的边。
现在小L想知道,如果他守在某一条边,是否一定能见到共价大爷。
然而长沙市总是不断的施工,也就是说,可能某个时刻某条边会断开,同时这个时刻一定也有某条新边会出现,且任意时刻图都满足任意两点间均存在恰好一条路径的条件。注意断开的边有可能和加入的新边连接着相同的两个端点。共价大爷的兴趣也会不断变化,所以S也会不断加入新点对或者删除原有的点对。当然,小L也有可能在任何时候向你提出守在某一条边是否一定能见到共价大爷的问题。你能回答小L的所有问题吗?

Http

UOJ

Tag

LCT,随机化

解决思路

dsl推荐的这道题,写了一晚上。两个人差不多想到了前面的大部分部分分,但仍然不知道到底怎么做。一看题解,真乃神题也。
考虑如果一个边\(x,y\)是共价大爷一定会经过的边,那么把\(x\)作为根,\(S\)中的每一对点中必然有一个出现在\(y\)的子树内。
这个怎么统计呢?总不能\(bitset\)吧。这时候看到随机化的标签,没错,可以给每一对点随机一个权值,求子树的异或和,若\(y\)的子树异或和与全局\(S\)中每一对点权值的异或和相等,那么就很有可能是对的。当权值区间取得\(10^9\)差不多就不会错了。
所以本题的思路是,对每一对点随机一个权值,\(LCT\)维护子树异或和,注意是子树,所以这里关系到虚子树的异或和,另外再记一个虚子树异或和即可,只在改变边的虚实关系的时候修改它。
最后需要注意的是,随机种子最好不要用常用的那些,容易被\(hack\)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=400100;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int rev;
    int key;
    int sum;//异或和(包括实虚子树)
    int vsum;//虚子树异或和
};

int n,m;
Splay_Data S[maxN];
int Stack[maxN];
int scnt=0,S1[maxN],S2[maxN],Sxor[maxN];

bool Isroot(int x);
void PushDown(int x);
void Update(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
void Makeroot(int x);
int Findroot(int x);
void Link(int x,int y);
void Cut(int x,int y);
int make(int l,int r);//得到一个l到r区间内的随机数
void Outp();

int main()
{
    srand(141936+141905);
    scanf("%d",&n);scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        Link(u,v);
    }
    int xorsum=0;
    for (int i=1;i<=m;i++)
    {
        int type;
        scanf("%d",&type);
        if (type==1)
        {
            int x,y,u,v;scanf("%d%d%d%d",&x,&y,&u,&v);
            Cut(x,y);Link(u,v);
        }
        if (type==2)
        {
            int x,y;scanf("%d%d",&x,&y);
            scnt++;S1[scnt]=x;S2[scnt]=y;Sxor[scnt]=make(1,1000000000);
            Makeroot(x);Splay(x);S[x].key^=Sxor[scnt];Update(x);
            Makeroot(y);Splay(y);S[y].key^=Sxor[scnt];Update(y);
            xorsum^=Sxor[scnt];
        }
        if (type==3)
        {
            int id;scanf("%d",&id);
            int x=S1[id],y=S2[id];
            Makeroot(x);Splay(x);S[x].key^=Sxor[id];Update(x);
            Makeroot(y);Splay(y);S[y].key^=Sxor[id];Update(y);
            xorsum^=Sxor[id];
        }
        if (type==4)
        {
            int x,y;scanf("%d%d",&x,&y);
            Makeroot(x);Access(y);Splay(y);
            if (S[x].sum==xorsum) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

bool Isroot(int x)
{
    int fa=S[x].fa;
    if ((S[fa].ch[0]==x)||(S[fa].ch[1]==x)) return 0;
    return 1;
}

void PushDown(int x)
{
    if (S[x].rev)
    {
        S[x].rev=0;
        int lson=S[x].ch[0],rson=S[x].ch[1];
        swap(S[lson].ch[0],S[lson].ch[1]);
        swap(S[rson].ch[0],S[rson].ch[1]);
        if (lson) S[lson].rev^=1;
        if (rson) S[rson].rev^=1;
    }
    return;
}

void Update(int x)
{
    S[x].sum=S[S[x].ch[0]].sum^S[S[x].ch[1]].sum^S[x].key^S[x].vsum;
    return;
}

void Rotate(int x)
{
    int y=S[x].fa,z=S[y].fa;
    int sx=(x==S[y].ch[1]);
    int sy=(y==S[z].ch[1]);
    S[x].fa=z;if (Isroot(y)==0) S[z].ch[sy]=x;
    S[y].ch[sx]=S[x].ch[sx^1];if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;
    S[y].fa=x;S[x].ch[sx^1]=y;
    Update(y);Update(x);return;
}

void Splay(int x)
{
    int now=x,stacktop=1;Stack[1]=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=S[now].fa;now=S[now].fa;
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=S[x].fa,z=S[y].fa;
        if (Isroot(y)==0)
            ((x==S[y].ch[0])^(y==S[z].ch[0]))?(Rotate(x)):Rotate(y);
        Rotate(x);
    }
    Update(x);return;
}

void Access(int x)
{
    int lastx=0;
    while (x)
    {
        Splay(x);S[x].vsum^=S[lastx].sum^S[S[x].ch[1]].sum;
        S[x].ch[1]=lastx;Update(x);
        lastx=x;x=S[x].fa;
    }
    return;
}

void Makeroot(int x)
{
    Access(x);Splay(x);S[x].rev^=1;swap(S[x].ch[0],S[x].ch[1]);
    return;
}

int Findroot(int x)
{
    Access(x);Splay(x);
    while (S[x].ch[0]) x=S[x].ch[0];
    return x;
}

void Link(int x,int y)
{
    Makeroot(x);Makeroot(y);S[y].vsum^=S[x].sum;
    S[x].fa=y;
    return;
}

void Cut(int x,int y)
{
    Makeroot(x);Access(y);Splay(y);
    S[x].fa=S[y].ch[0]=0;Update(x);Update(y);
    return;
}

int make(int l,int r)
{
    double dou=1.0*rand()/RAND_MAX;
    return dou*(r-l+1)+l;
}

void Outp()
{
    printf("id fa ls rs       key        sum        vsum\n");
    for (int i=0;i<=n;i++) printf("%2d%3d%3d%3d%10d%11d%12d\n",i,S[i].fa,S[i].ch[0],S[i].ch[1],S[i].key,S[i].sum,S[i].vsum);
    cout<<endl;
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[UOJ207]共价大爷游长沙(LCT,随机化)


HNCJ OIer 一枚