BZOJ 1180/2843: [CROATIAN2009]OTOCI – [LCT][模版]

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

题解 :

有关LCT的讲解,请见本人给 OI-Wiki 的供稿 :LCT!

代码 :

#include 
#include 
#include 
#include 
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1] == x)
using namespace std;
const int N = 31000;
int ch[N][2], f[N], sum[N], tag[N], val[N];
#define isRoot(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
inline void pd(int p) {
    if(tag[p]) {
        swap(ch[ls][0], ch[ls][1]);
        swap(ch[rs][0], ch[rs][1]);
        tag[ls] ^= 1, tag[rs] ^= 1;
        tag[p] = 0;
    }
}
void Up(int p) {
    if(!isRoot(p)) Up(f[p]);
    pd(p);
}
inline void pu(int p) {
    sum[p] = sum[ls] + sum[rs] + val[p];
}
inline 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;
    pu(y), pu(x);
}
void Splay(int p) {
    Up(p);
    for(int fa; fa = f[p], !isRoot(p); Rotate(p)) 
        if(!isRoot(fa)) Rotate(get(p) == get(fa) ? fa : p);
}
void Access(int p) {
    for(int t = 0; p; t = p, p = f[p]) {
        Splay(p), ch[p][1] = t, pu(p);
    }
}
inline void MakeRoot(int p) {
    Access(p);
    Splay(p), swap(ls, rs);
    tag[p] ^= 1;
}
inline void Link(int x, int p) {
    MakeRoot(x), f[x] = p, Splay(x);
}
int find(int p) {
    Access(p), Splay(p);
    while(ls) pd(p), p = ls;
    return p;
}
int main() {
    int n, m;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &val[i]);
    scanf("%d", &m);
    while(m--) {
        char opt[20];
        int x, p;
        scanf("%s%d%d", opt, &x, &p);
        if(opt[0]=='b') {
            int dx = find(x), dy = find(p);
            if(dx!=dy) {
                puts("yes");Link(x, p);
            }
            else {
                puts("no");
            }
        }
        else if(opt[0]=='p'){
            MakeRoot(x);Access(x);Splay(x);
            val[x]=sum[x]=p;
        }
        else {
            int dx = find(x), dy = find(p);
            if(dx!=dy) {
                puts("impossible");
            }
            else {
                MakeRoot(x);Access(p);Splay(p);
                printf("%d\n", sum[p]);
            }
        }
    }
}

发表评论

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