BZOJ 1180: [CROATIAN2009]OTOCI

1180: [CROATIAN2009]OTOCI

Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 989 Solved: 611
[Submit][Status][Discuss]

Description

给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作：

1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。

2、penguins A X：将结点A对应的权值wA修改为X。

3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。

给出q个操作，要求在线处理所有操作。数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

Input

第一行包含一个整数n(1<=n<=30000)，表示节点的数目。

第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。

第三行包含一个整数q(1<=n<=300000)，表示操作的数目。

以下q行，每行包含一个操作，操作的类别见题目描述。

Output

输出所有bridge操作和excursion操作对应的输出，每个一行。

Sample Input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

Sample Output

4
impossible
yes
6
yes
yes
15
yes
15
16

HINT

任意时刻每个节点对应的权值都是1到1000的整数。

Source

[Submit][Status][Discuss]

又是一道LCT模板题，Splay上维护子树权值和，就相当于维护了路径权值和。

  1 #include <cstdio>
  2 
  3 template <class T>
  4 inline void swap(T &a, T &b)
  5 {
  6     T c;
  7     
  8     c = a;
  9     a = b;
 10     b = c;
 11 }
 12 
 13 const int mxn = 30005;
 14 
 15 int n, m;
 16 
 17 struct node
 18 {
 19     int val;
 20     int sum;
 21     node *son[2];
 22     node *father;
 23     bool reverse;
 24     
 25     inline node(int v = 0)
 26     {
 27         val = v;
 28         sum = v;
 29         son[0] = NULL;
 30         son[1] = NULL;
 31         father = NULL;
 32         reverse = false;
 33     }
 34     
 35     inline void update(void)
 36     {
 37         sum = val;
 38         
 39         if (son[0])sum += son[0]->sum;
 40         if (son[1])sum += son[1]->sum;
 41     }
 42     
 43     inline bool isRoot(void)
 44     {
 45         if (father == NULL)
 46             return true;
 47         
 48         if (father->son[0] == this)
 49             return false;
 50         if (father->son[1] == this)
 51             return false;
 52         
 53         return true;
 54     }
 55     
 56     inline void pushDown(void)
 57     {
 58         if (reverse)
 59         {
 60             reverse = false;
 61             
 62             swap(son[0], son[1]);
 63             
 64             if (son[0])son[0]->reverse ^= true;
 65             if (son[1])son[1]->reverse ^= true;
 66         }
 67     }
 68 }tree[mxn];
 69 
 70 inline void connect(node *f, node *t, bool k)
 71 {
 72     if (t != NULL)t->father = f;
 73     if (f != NULL)f->son[k] = t;
 74 }
 75 
 76 inline void rotate(node *t)
 77 {
 78     node *f = t->father;
 79     node *g = f->father;
 80     
 81     bool s = f->son[1] == t;
 82     
 83     connect(f, t->son[!s], s);
 84     connect(t, f, !s);
 85     
 86     t->father = g;
 87     if (g && g->son[0] == f)g->son[0] = t;
 88     if (g && g->son[1] == f)g->son[1] = t;
 89     
 90     f->update();
 91     t->update();
 92 }
 93 
 94 inline void push(node *t)
 95 {
 96     static node *stk[mxn];
 97     
 98     int top = 0;
 99     
100     stk[top++] = t;
101     
102     while (!t->isRoot())
103         stk[top++] = t = t->father;
104     
105     while (top)stk[--top]->pushDown();
106 }
107 
108 inline void splay(node *t)
109 {
110     push(t);
111     
112     while (!t->isRoot())
113     {
114         node *f = t->father;
115         node *g = f->father;
116         
117         if (f->isRoot())
118             rotate(t);
119         else
120         {
121             bool a = f && f->son[1] == t;
122             bool b = g && g->son[1] == f;
123             
124             if (a == b)
125                 rotate(f), rotate(t);
126             else
127                 rotate(t), rotate(t);
128         }
129     }
130 }
131 
132 inline void access(node *t)
133 {
134     node *p = NULL;
135     
136     while (t != NULL)
137     {
138         splay(t);
139         t->son[1] = p, t->update();
140         p = t, t = t->father;
141     }
142 }
143 
144 inline void makeRoot(node *t)
145 {
146     access(t), splay(t), t->reverse ^= true;
147 }
148 
149 inline void link(node *t, node *f)
150 {
151     makeRoot(t), t->father = f;
152 }
153 
154 inline void cut(node *t)
155 {
156     splay(t);
157     
158     if (t->son[0])t->son[0]->father = NULL;
159     if (t->son[1])t->son[1]->father = NULL;
160     
161     t->son[0] = t->son[1] = NULL, t->update();
162 }
163 
164 inline node *find(node *t)
165 {
166     access(t), splay(t);
167     
168     node *r = t;
169     
170     while (r->son[0])
171         r = r->son[0];
172     
173     return r;
174 }
175 
176 signed main(void)
177 {
178     scanf("%d", &n);
179     
180     for (int i = 1, v; i <= n; ++i)
181         scanf("%d", &v), tree[i] = node(v);
182     
183     scanf("%d", &m);
184     
185     while (m--)
186     {
187         static int x, y;
188         static char s[50];
189         
190         scanf("%s%d%d", s, &x, &y);
191         
192         if (s[0] == 'b')
193         {
194             if (find(tree + x) == find(tree + y))
195                 puts("no");
196             else
197                 puts("yes"), link(tree + x, tree + y);
198         }
199         else if (s[0] == 'p')
200         {
201             access(tree + x), splay(tree + x);
202             tree[x].val = y, tree[x].update();
203         }
204         else
205         {
206             if (find(tree + x) != find(tree + y))
207                 puts("impossible");
208             else
209             {
210                 makeRoot(tree + x), access(tree + y), splay(tree + y);
211                 printf("%d
", tree[y].sum);
212             }
213         }
214     }
215 }

@Author: YouSiki