백준21973 남극 탐험

작성일 | In

문제 링크

  • http://icpc.me/21973

사용 알고리즘

  • Link/Cut Tree

시간복잡도

  • $O(Q \log N)$

풀이

링크컷 트리 연습 문제입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

struct Info{
    ll val;
    Info() : Info(0) {}
    Info(ll val) : val(val) {}
    void set(ll v){ val = v; }
    Info operator + (const Info &t) const { return Info(val + t.val); }
};
struct Node{
    Node *l, *r, *p;
    int sz; bool flip; Info v, sum;
    Node() : Node(Info()) {}
    Node(Info v) : v(v), sum(v), flip(false) { l = r = p = nullptr; sz = 1; }
    bool IsRoot() const { return !p || (this != p->l && this != p->r); }
    bool IsLeft() const { return p && this == p->l; }
    void Rotate(){
        if(IsLeft()) r && (r->p = p), p->l = r, r = p;
        else l && (l->p = p), p->r = l, l = p;
        if(!p->IsRoot()) (p->IsLeft() ? p->p->l : p->p->r) = this;
        auto t = p; p = t->p; t->p = this;
        t->Update(); Update();
    }
    void Update(){
        sz = 1; sum = v;
        if(l) sz += l->sz, sum = sum + l->sum;
        if(r) sz += r->sz, sum = sum + r->sum;
    }
    void Push(){
        if(flip){
            swap(l, r); flip = false;
            if(l) l->flip ^= 1;
            if(r) r->flip ^= 1;
        }
    }
};
void Splay(Node *x){
    for(; !x->IsRoot(); x->Rotate()){
        if(!x->p->IsRoot()) x->p->p->Push(); x->p->Push(); x->Push();
        if(!x->p->IsRoot()) (x->IsLeft() ^ x->p->IsLeft() ? x : x->p)->Rotate();
    }
    x->Push();
}
void Access(Node *x){
    Splay(x); x->r = nullptr; x->Update();
    for(auto y=x; x->p; Splay(x)){
        y = x->p; Splay(y);
        y->r = x; y->Update();
    }
}
void Link(Node *p, Node *c){
    Access(c); Access(p);
    c->l = p; p->p = c;
    c->Update();
}
void Cut(Node *x){
    Access(x);
    x->l->p = nullptr;
    x->l = nullptr;
    x->Update();
}
Node* GetLCA(Node *x, Node *y){
    Access(x); Access(y); Splay(x);
    return x->p ? x->p : x;
}
Node* GetRoot(Node *x){
    Access(x);
    while(x->l) x = x->l;
    Splay(x);
    return x;
}
Node* GetPar(Node *x){
    Access(x);
    if(!x->l) return nullptr;
    x = x->l; while(x->r) x = x->r;
    Splay(x);
    return x;
}
int GetDepth(Node *x){
    Access(x);
    if(x->l) return x->l->sz;
    return 0;
}
void MakeRoot(Node *x){
    Access(x); Splay(x);
    x->flip ^= 1;
}
bool IsConnect(Node *x, Node *y){
    return GetRoot(x) == GetRoot(y);
}
void ChangeValue(Node *x, const Info val){
    Access(x);
    x->v = val;
    x->Update();
}
Info VertexQuery(Node *x, Node *y){
    Node *l = GetLCA(x, y);
    Info ret = l->v;
    Access(x); Splay(l);
    if(l->r) ret = ret + l->r->sum;
    Access(y); Splay(l);
    if(l->r) ret = ret + l->r->sum;
    return ret;
}

int N, Q;
Node T[30303];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1,t; i<=N; i++) cin >> t, ChangeValue(T+i, t);
    cin >> Q;
    while(Q--){
        string op; int a, b; cin >> op >> a >> b;
        if(op[0] == 'b'){
            if(IsConnect(T+a, T+b)){ cout << "no" << endl; continue; }
            cout << "yes" << endl;
            MakeRoot(T+a); MakeRoot(T+b);
            Link(T+a, T+b);
        }
        else if(op[0] == 'p'){
            ChangeValue(T+a, b);
        }
        else{
            if(!IsConnect(T+a, T+b)) cout << "impossible" << endl;
            else cout << VertexQuery(T+a, T+b).val << endl;
        }
    }
}