BZOJ 2002: [HNOI2010]弹飞绵羊 – [LCT]


题目传送门(BZOJ)
>原文链接<

题解 :

我们建立一个虚拟点n+1, 设弹到它就算弹出去.

修改 :

对于一个点x, 其弹力为k, 那么相当于xx+k有一条边,

对于修改, 相当于断掉这条边, 再链接一条(x, x+k’)(k’是新的弹力)

对于x+k > n的, 这个就会弹出去, 我们向n+1连边.

就这样, 初始化和修改已经有了方法, 考虑如何查询;

查询 :

我们令x指向的边是x的父亲(连边操作都在LCT中完成),

那么查询一个点弹几次会弹出去就是查询它跳fa能跳多少次跳到n+1

所以我们$makeRoot(n+1)$

我们再$Access(x)$, 这样这条路径$(n+1, x)$就被我们拿出来当成一棵$Splay$了,

由于$Splay$的关键字是深度, 所以我们可以直接把$x$Splay上去, 这样, $x$的左子树大小, 就是这条链上深度比它浅的点的数量, 也就是要弹多少次才能弹出去, 所以$siz[ls]$就是答案啦.

代码 :

#include 
using namespace std;
#define ls ch[p][0]
#define rs ch[p][1]
const int N = 210000;
int ch[N][2], f[N], siz[N], tag[N], nxt[N];
class Input_Output {
    char buf[100000], *p1, *p2;
    char Nc() {
        return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin)), p1==p2?EOF:*p1++;
    }
public:
    int Read() {
        int x = 0;char c = Nc();
        while(!isdigit(c)) c = Nc();
        while(isdigit(c)) x=(x<<3)+(x<<1)+c-48, c=Nc();
        return x;
    }
}I_O;
class Link_Cut_Tree {
private:
    int Get(int p) {
        return ch[f[p]][1] == p;
    }
    bool IsRoot(int p) {
        return ch[f[p]][1] != p&&ch[f[p]][0]!=p;
    }
    void PushUp(int p) {
        siz[p] = siz[ls]+siz[rs]+1;
    }
    void PushDown(int p) {
        if(tag[p]) {
            tag[p] = 0;
            swap(ch[ls][0], ch[ls][1]);
            swap(ch[rs][0], ch[rs][1]);
            tag[ls] ^= 1, tag[rs] ^= 1;
        }
        return;
    }
    void Update(int p) {
        if(!IsRoot(p)) Update(f[p]);
        PushDown(p);
    }
    void Rotate(int x) {
        int y = f[x], z = f[y], k = Get(x);
        if(!IsRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k]; f[ch[y][k]] = y;
        ch[x][!k] = y; f[y] = x, f[x] = z;
        PushUp(y), PushUp(x);
    }
public:
    void Splay(int x) {
        Update(x);
        for(int fa;fa = f[x], !IsRoot(x);Rotate(x))
            if(!IsRoot(fa)) Rotate(Get(x) == Get(fa)?fa:x);
    }
    void Access(int x) {
        for(int fa = 0; x; fa = x, x = f[x]) Splay(x), ch[x][1] = fa, PushUp(x);
    }
    void MakeRoot(int p) {
        Access(p);Splay(p);
        swap(ls, rs);
        tag[p] ^= 1;
    }
    void Split(int x, int y) {
        MakeRoot(x);
        Access(y);
        Splay(y);
    }
    int Find(int p) {
        Access(p);
        Splay(p);
        while(ls) PushDown(p), p = ls;
        Splay(p);
        return p;
    }
    void Link(int x, int p) {
        MakeRoot(x);
        f[x] = p;
        Splay(x);
    }
    void Cut(int x, int p) {
        Split(x, p);
        ls = f[x] = 0;
    }

}LCT;
class Init_And_Solve {
    int n, m;
public:
    void Init() {
        n = I_O.Read();
        for(int i = 1; i <= n; i ++ ) {
            int x = I_O.Read();
            f[i] = x+i;
            siz[i] = 1;
            if(f[i]>n+1) f[i] = n+1;
            nxt[i] = f[i];
        }
        siz[n+1]=1;
    }
    void Solve() {
        m = I_O.Read();
        for(int i = 1; i <= m; i ++ ) {
            int opt = I_O.Read();
            if(opt == 1) {
                int x = I_O.Read();
                LCT.MakeRoot(n+1);
                x++;
                LCT.Access(x);
                LCT.Splay(x);
                printf("%d\n", siz[ch[x][0]]);
            }
            else {
                int x = I_O.Read(), y = I_O.Read();
                x ++ ;
                int to = min(n+1, x+y);
                LCT.Cut(x, nxt[x]);
                LCT.Link(x, to);
                nxt[x] = to;
            }
        }
    }
}init;
int main() {
    init.Init();
    init.Solve();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注