「BZOJ2002」「HNOI2010」弹飞绵羊

发布于 2019-01-29  389 次阅读


题目描述

题目链接
某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$,当绵羊达到第 $i$ 个装置时,它会往后弹 $k_i$ 步,达到第 $i+k_i$ 个装置,若不存在第 $i+k_i$ 个装置,则绵羊被弹飞。绵羊想知道当它从第 $i$ 个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey 可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。

题解

LCT 裸题。
我们不妨设一个超级点 $T$,如果在某一个装置会被弹飞的话我们就把这个装置与 $T$ 链接,否则就连到能连的那个装置上。注意到题目保证弹力系数为正整数,所以这样连会得到一个森林,用 LCT 维护一下每个森林的 $size$,查询的时候直接把这个点和超级点拉到一个路径上询问 $size$ 就可以了。
修改操作也很好做......首先断开原来这个点和其他点的连边,然后按照修改后的系数连就可以了。
时间复杂度 $O(n log^2 n)$$

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fi first
#define lc (ch[x][0])
#define se second
#define U unsigned
#define rc (ch[x][1])
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200000+5;

int ch[MAXN][2],tag[MAXN],size[MAXN],val[MAXN],f[MAXN];

bool nroot(int x){
    return ch[f[x]][0] == x || ch[f[x]][1] == x;
}

inline void reverse(int x){
    std::swap(lc,rc);tag[x] ^= 1;
}

inline void pushdown(int x){
    if(tag[x]){
        if(lc) reverse(lc);
        if(rc) reverse(rc);
        tag[x] = 0;
    }
}

inline void pushup(int x){
    size[x] = 1;
    if(lc) size[x] += size[lc];
    if(rc) size[x] += size[rc];
}

inline void rotate(int x){
    int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
    if(nroot(y)) ch[z][ch[z][1]==y] = x;
    ch[x][!k] = y;ch[y][k] = w;
    if(w) f[w] = y;
    f[y] = x;f[x] = z;
    pushup(y);
}

int st[MAXN];
inline void splay(int x){
    int y = x,z;st[z = 1] = y;
    while(nroot(y)) st[++z] = y = f[y];
    while(z) pushdown(st[z--]);
    while(nroot(x)){
        y = f[x];z = f[y];
        if(nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y) ? x : y);
        rotate(x);
    }
    pushup(x);
}

inline void access(int x){
    for(int y = 0;x;x = f[y = x]){
        splay(x);rc = y;pushup(x);
    }
}

inline void makeroot(int x){
    access(x);splay(x);reverse(x);
}

inline int findroot(int x){
    access(x);splay(x);
    while(lc) pushdown(x),x = lc;
    splay(x);
    return x;
}

inline void link(int x,int y){
    makeroot(x);
    if(findroot(y) != x) f[x] = y;
}

inline void cut(int x,int y){
    makeroot(x);access(y);splay(y);
    f[x] = ch[y][0] = 0;pushup(y);
}

inline int calc(int x,int y){
    makeroot(x);access(y);splay(y);
    return size[y];
}

int main(){
    int N,M;scanf("%d",&N);
    FOR(i,1,N+1) size[i] = 1;
    int T = N+1;
    FOR(i,1,N){
        scanf("%d",val+i);
        if(i+val[i] <= N) link(i,i+val[i]);
        else link(i,T);
    }
    scanf("%d",&M);
    while(M--){
        int opt,x,y;scanf("%d%d",&opt,&x);x++;
        if(opt == 1){
            printf("%d\n",calc(x,T)-1);
        }
        else{
            scanf("%d",&y);cut(x,x+val[x]<=N?x+val[x]:T);
            link(x,x+y<=N?x+y:T);
            val[x] = y;
        }
    }
    return 0;
}

一个OIer。