mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 4668: 冷战 LCT

1946 年 3 月 5 日,英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”,正式拉开了冷战序幕。
美国和苏联同为世界上的“超级大国”,为了争夺世界霸权,两国及其盟国展开了数十年的斗争。在这段时期,虽然分歧和冲突严重,但双方都尽力避免世界范围的大规模战争(第三次世界大战)爆发,其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行,即“相互遏制,不动武力”,因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张,因此他需要时刻关注着苏联的各个活动,避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂,但由于规划不当,一开始这些军工厂之间是不存在铁路的,为了使武器制造更快,苏联决定修建若干条道路使得某些军工厂联通。
Reddington 得到了苏联的修建日程表,并且他需要时刻关注着某两个军工厂是否联通,以及最早在修建哪条道路时会联通。具体而言,现在总共有 M 个操作,操作分为两类:
• 0 u v,这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路,注意铁路都是双向的;
• 1 u v, Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通,假如到这次操作都没有联通,则输出 0;
作为美国最强科学家, Reddington 需要你帮忙设计一个程序,能满足他的要求。

Input

第一行两个整数 N, M。 接下来 M 行,每行为 0 u v 或 1 u v 的形式。 数据是经过加密的,对于每次加边或询问,真正的 u, v 都等于读入的 u, v 异或上上一次询问的答案。一开始这个值为 0。 1 ≤ N, M ≤ 500000,解密后的 u, v 满足 1 ≤ u, v ≤ N, u 不等于 v

Output

对于每次 1 操作,输出 u, v 最早在加入哪条边后会联通,若到这个操 作时还没联通,则输出 0。

Sample Input

5 9
0 1 4
1 2 5
0 2 4
0 3 4
1 3 1
0 7 0
0 6 1
0 1 6
1 2 6

Sample Output

0
3
5

Solution

直接用 LCT 维护动态最小生成树就行了,虽然很暴力,但能 AC。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

const int N=1000001;

struct node
{
    node *c[2],*fa;
    int val,ma;
    bool rev;
    inline void rotate(bool f);
    inline void pushdown();
    inline void pushup();
}s[N],_null,*null=&_null;

inline void node::pushdown()
{
    if(fa->c[0]==this||fa->c[1]==this)
        fa->pushdown();
    if(rev)
    {
        rev=0;
        std::swap(c[0],c[1]);
        if(c[0]!=null)c[0]->rev=!c[0]->rev;
        if(c[1]!=null)c[1]->rev=!c[1]->rev;
    }
}

inline void node::rotate(bool f)
{
    fa->c[f]=c[!f];
    c[!f]=fa;
    fa=c[!f]->fa;
    if(c[!f]->fa->c[1]==c[!f])
        c[!f]->fa->c[1]=this;
    else if(c[!f]->fa->c[0]==c[!f])
        c[!f]->fa->c[0]=this;
    c[!f]->fa=this;
    c[!f]->c[f]->fa=c[!f];
    c[!f]->pushup();
}

inline void node::pushup()
{
    ma=val;
    if(c[0]!=null)repr(ma,c[0]->ma);
    if(c[1]!=null)repr(ma,c[1]->ma);
}

inline void init(node *x,int v)
{
    x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null;
}

inline void splay(node *a)
{
    a->pushdown();
    while(a->fa->c[0]==a||a->fa->c[1]==a)
        a->rotate(a==a->fa->c[1]);
    a->pushup();
}

inline void access(node *a)
{
    node *x=null;
    while(a!=null)
    {
        splay(a);
        a->c[1]=x;
        a->pushup();
        x=a,a=a->fa;
    }
}

inline void movetoroot(node *x)
{
    access(x);
    splay(x);
    x->rev=!x->rev;
}

inline void link(node *x,node *y)
{
    movetoroot(x);
    x->fa=y;
}

inline void cut(node *x,node *y)
{
    movetoroot(x);
    access(y);
    splay(y);
    x->fa=null;
    y->c[0]=null;
    y->pushup();
}

inline void split(node *x,node *y)
{
    movetoroot(x),access(y),splay(y);
}

inline node* findroot(node *x)
{
    while(x->fa!=null)
        x=x->fa;
    return x;
}

int main()
{
    int n,m,lstans=0,opt,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        init(s+i,0);
    for(int i=1,ec=0;i<=m;i++)
    {
        scanf("%d%d%d",&opt,&x,&y);
        x^=lstans,y^=lstans;
        if(opt==0)
        {
            ec++;
            if(findroot(s+x)!=findroot(s+y))
            {
                init(s+n+ec,ec);
                link(s+x,s+n+ec);
                link(s+y,s+n+ec);
            }
        }
        else
        {
            split(s+x,s+y);
            if(findroot(s+x)==s+y)
                lstans=s[y].ma;
            else
                lstans=0;
            printf("%d\n",lstans);
        }
    }
}

日期: 2016-11-09

标签: BZOJ LCT

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/72/ 查看。