双倍经验双倍的幸福。。。
所以另一道是300大洋的世界T_T。。。虽然题目是一样的，不过2843数据范围小了一点。。。
都是lct基本操作
#include<cstdio>
#include<iostream>
#include<math.h>
using namespace std;
const int maxn=;
struct zs{
int c[],fa,sum,val;
bool rev;
}tree[maxn];
int i,j,x,y,n,m;
int stack[maxn];
char id[];
inline bool isroot(int x){return tree[tree[x].fa].c[]!=x&&tree[tree[x].fa].c[]!=x;
}
inline void update(int x){tree[x].sum=tree[tree[x].c[]].sum+tree[x].val+tree[tree[x].c[]].sum;
}
inline void pushdown(int x){
if(!tree[x].rev)return;
int l=tree[x].c[],r=tree[x].c[];
if(l)tree[l].rev^=;if(r)tree[r].rev^=;tree[x].rev^=;
swap(tree[x].c[],tree[x].c[]);
}
inline void rotate(int x){
int fa=tree[x].fa,gfa=tree[fa].fa;
if(!isroot(fa))tree[gfa].c[tree[gfa].c[]==fa]=x;
int l=tree[fa].c[]==x,r=l^;
tree[fa].c[l]=tree[x].c[r];tree[x].c[r]=fa;
tree[fa].fa=x;tree[x].fa=gfa;tree[tree[fa].c[l]].fa=fa;
update(fa);update(x);
}
void splay(int x){
int top=,tmp=x;stack[++top]=x;
while(!isroot(tmp))stack[++top]=tree[tmp].fa,tmp=tree[tmp].fa;
while(top)pushdown(stack[top]),top--;
int fa,gfa;
while(!isroot(x)){
fa=tree[x].fa,gfa=tree[fa].fa;
if(!isroot(fa))
if((tree[gfa].c[]==fa)^(tree[fa].c[]==x))rotate(x);
else rotate(fa);
rotate(x);
}
}
inline void access(int x){
int son=;
while(x){
splay(x);tree[x].c[]=son;
update(x);son=x;x=tree[x].fa;
}
}
inline void makeroot(int x){
access(x);splay(x);tree[x].rev^=;
}
inline void cut(int x,int y){
makeroot(x);access(y);splay(y);tree[y].c[]=tree[x].fa=;
}
inline void link(int x,int y){
makeroot(x);tree[x].fa=y;
}
inline int getfa(int x){
access(x);splay(x);
while(tree[x].c[]){x=tree[x].c[];pushdown(x);}
splay(x);return x;
}
inline int query(int x,int y){
makeroot(x);access(y);splay(y);
return tree[y].sum;
}
inline void change(int x,int val){
makeroot(x);tree[x].val=val;update(x);
}
int main(){
scanf("%d",&n);for(i=;i<=n;i++)scanf("%d",&tree[i].val),tree[i].sum=tree[i].val;
scanf("%d",&m);
while(m--){
scanf("%s%d%d",id,&x,&y);
if(id[]=='e'){
if(getfa(x)!=getfa(y))printf("impossible\n");else printf("%d\n",query(x,y));
}else if(id[]=='b'){
if(getfa(x)==getfa(y))printf("no\n");
else printf("yes\n"),link(x,y);
}else if(id[]=='p')change(x,y);
}
return ;
}
16.1.8：重写了一发
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int ch[maxn][],fa[maxn],sum[maxn],num[maxn],st[maxn];
int i,j,x,y,n,m;
bool rev[maxn]; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
} inline bool isrt(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}
inline void upd(int x){sum[x]=sum[ch[x][]]+num[x]+sum[ch[x][]];}
inline void pushdown(int x){
if(!rev[x])return;
rev[x]=,swap(ch[x][],ch[x][]),rev[ch[x][]]^=,rev[ch[x][]]^=;
}
inline void rotate(int x){
int f=fa[x],gfa=fa[f],l=ch[f][]==x,r=l^;
if(!isrt(f))ch[gfa][ch[gfa][]==f]=x;
ch[f][l]=ch[x][r],ch[x][r]=f,fa[x]=gfa,fa[f]=x,fa[ch[f][l]]=f;
sum[x]=sum[f],upd(f);
}
void splay(int x){
int f,gfa;
for(st[st[]=]=f=x;!isrt(f);)st[++st[]]=(f=fa[f]);
while(st[])pushdown(st[st[]--]);
for(f=fa[x],gfa=fa[f];!isrt(x);rotate(x),f=fa[x],gfa=fa[f])
if(!isrt(f))rotate(((ch[f][]==x)^(ch[gfa][]==f))?x:f);
}
inline void access(int x){
for(int t=;x;t=x,x=fa[x])splay(x),ch[x][]=t,upd(x);
}
inline void makert(int x){
access(x),splay(x),rev[x]^=;
}
void link(int x,int y){
makert(x),fa[x]=y;if(!(x&))splay(x);
}
inline int getfa(int x){
for(access(x),splay(x);ch[x][];x=ch[x][]);
return x;
}
int main(){
n=read();for(i=;i<=n;i++)num[i]=read();
m=read();char id;
while(m--){
for(id=getchar();id<'a'||id>'z';id=getchar());
x=read(),y=read();
if(id=='b')if(getfa(x)!=getfa(y))link(x,y),puts("yes");else puts("no");
if(id=='e')if(getfa(x)==getfa(y))makert(x),access(y),splay(y),printf("%d\n",sum[y]);else puts("impossible");
if(id=='p')makert(x),num[x]=y,upd(x);
}
return ;
}
2843: 极地旅行社
Time Limit: 10 Sec Memory Limit: 256 MB
Description
不久之前，Mirko建立了一个旅行社，名叫“极地之梦”。这家旅行社在北极附近购买了N座冰岛，并且提供观光服务。当地最受欢迎的当然是帝企鹅了，这些小家伙经常成群结队的游走在各个冰岛之间。
Mirko的旅行社遭受一次重大打击，以至于观光游轮已经不划算了。旅行社将在冰岛之间建造大桥，并用观光巴士来运载游客。Mirko希望开发一个电脑程序来管理这些大桥的建造过程，以免有不可预料的错误发生。
这些冰岛从1到N标号。一开始时这些岛屿没有大桥连接，并且所有岛上的帝企鹅数量都是知道的。每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。
你的程序需要处理以下三种命令：
1."bridge A B"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，这项命令被接受，当且仅当A与B不联通。若这项命令被接受，你的程序需要输出"yes"，之后会建造这座大桥。否则，你的程序需要输出"no"。
2."penguins A X"——根据可靠消息，岛屿A此时的帝企鹅数量变为X。这项命令只是用来提供信息的，你的程序不需要回应。
3."excursion A B"——一个旅行团希望从A出发到B。若A与B连通，你的程序需要输出这个旅行团一路上所能看到的帝企鹅数量（包括起点A与终点B），若不联通，你的程序需要输出"impossible"。
Input
第一行一个正整数N，表示冰岛的数量。
第二行N个范围[0, 1000]的整数，为每座岛屿初始的帝企鹅数量。
第三行一个正整数M，表示命令的数量。
接下来M行即命令，为题目描述所示。
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
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
impossible
yes
6
yes
yes
15
yes
15
16
HINT
1<=N<=30000，1<=M<=100000（bzoj2843）
1<=n<=30000, 1<=m<=300000 （bzoj1180）