维护一个n个点的初始没有边的无向图, m个操作, 支持: - 查询a,b连通性并连一条边 (已连通则忽略) - 修改某点点权 - 查询a,b路径上点权之和, 或报告不连通
(1≤n≤3*10^4, 1≤m≤10^5, 点权是[0,1000]内的整数) 由于没有删除操作, 离线, 建出最终的树, 树链剖分即可. 也可以直接丢一个LCT.
const int N = 3e4;
struct Node {
Node* ch[2], * fa;
int t, v, sum;
bool rev;
Node();
void setf(Node* f, int _t)
{
t = _t;
fa = f;
t >= 0 ? f->ch[t] = this : 0;
}
void reverse()
{
rev ^= 1;
swap(ch[0], ch[1]);
ch[0]->t = 0;
ch[1]->t = 1;
}
void down()
{
if (rev) {
rev = false;
ch[0]->reverse();
ch[1]->reverse();
}
}
void up()
{
sum = v + ch[0]->sum + ch[1]->sum;
}
} nodes[N+1], * nil = nodes;
Node::Node(): fa(0), t(-1), v(0), sum(0), rev(false)
{
ch[0] = ch[1] = nil;
}
inline void rot(Node* y)
{
Node* x = y->fa;
int t = y->t;
y->setf(x->fa, x->t);
y->ch[t^1]->setf(x, t);
x->setf(y, t^1);
x->up();
}
void splay(Node* x)
{
Node* y;
static Node* S[N];
int top = 0;
for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
for (y->down(); top; S[--top]->down()) ;
while (x->t >= 0) {
if ((y = x->fa)->t >= 0)
rot(x->t ^ y->t ? x : y);
rot(x);
}
x->up();
}
void access(Node* x)
{
for (Node* y = nil; x; y = x, x = x->fa) {
splay(x);
x->ch[1]->t = -1;
y->setf(x, 1);
x->up();
}
}
inline void make_root(Node* x)
{
access(x);
splay(x);
x->reverse();
}
Node* get_root(Node* x)
{
access(x);
splay(x);
while (x->ch[0] != nil) {
//x->down();
x = x->ch[0];
}
return x;
}
inline bool link(Node* x, Node* y)
{
make_root(x);
if (get_root(y) == x) return false;
x->setf(y, -1);
return true;
}
inline void modify(Node* x, int v)
{
access(x);
splay(x);
x->v = v;
x->up();
}
inline int query(Node* x, Node* y)
{
make_root(x);
return get_root(y) == x ? y->sum : -1;
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 1, n+1) {
scanf("%d", &nodes[i].v);
nodes[i].sum = nodes[i].v;
}
int m;
scanf("%d", &m);
while (m--) {
char s[10];
int x, y, ret;
scanf("%s%d%d", s, &x, &y);
switch (s[0]) {
case 'b':
puts(link(nodes+x, nodes+y) ? "yes" : "no");
break;
case 'p':
modify(nodes+x, y);
break;
default:
ret = query(nodes+x, nodes+y);
if (ret == -1)
puts("impossible");
else
printf("%d\n", ret);
}
}
return 0;
}