题解 P4312 【[COCI 2009] OTOCI / 极地旅行社】

· · 题解

给出q个操作，要求在线处理所有操作

emm....强制在线咋做啊，窝不会LCT咋办啊qwq

然而好像并没有强制在线？？

所以离线建树，用树剖套树状数组维护

Link操作咋办？

直接并查集就好了反正没有Cut操作泥萌用什么LCTqwq

时间复杂度 O(nlog_{2}^{2}n) 比LCT慢一个 log

然而由于树剖和树状数组的极小常数，这份代码跑得飞快，稳稳的拿到了Rank1

代码：(比LCT好写多了qwq)

#include<bits/stdc++.h>
using namespace std;
const int N=30001;
char s[9];
struct E{int u,nxt;}e[N*2];  //  无向边*2
int num,fa[N],siz[N],dep[N],ord[N],son[N],top[N];
int n,a[N],f[N],t[N],p[N],z[N*10],x[N*10],y[N*10];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}  //  并查集
inline void add(int x,int y){e[++num]=(E){y,p[x]},p[x]=num;}
inline void upd(int x,int y){for(int i=x;i<=n;i+=i&-i) t[i]+=y;}
inline int sum(int x){int s=0;for(int i=x;i;i-=i&-i) s+=t[i];return s;}  //  树状数组
void dfs1(int s){
    int sz=0;
    siz[s]=1;
    for(int i=p[s];i;i=e[i].nxt){
        if(e[i].u==fa[s]) continue;
        int u=e[i].u;
        fa[u]=s,dep[u]=dep[s]+1,dfs1(u),siz[s]+=siz[u];
        if(siz[u]>sz) sz=siz[u],son[s]=u;
    }
}
void dfs2(int s){
    ord[s]=++num;
    top[s]=son[fa[s]]!=s?s:top[fa[s]];
    if(son[s]) dfs2(son[s]);
    for(int i=p[s];i;i=e[i].nxt)
        if(e[i].u!=son[s]&&e[i].u!=fa[s]) dfs2(e[i].u);
}
int main(){
    int m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=i;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s%d%d",s,&x[i],&y[i]),z[i]=s[0]=='p'?1:s[0]=='e'?2:0;
        if(z[i]==2&&find(x[i])!=find(y[i])) z[i]=4;
        if(!z[i]&&find(x[i])!=find(y[i]))
            add(x[i],y[i]),add(y[i],x[i]),f[f[x[i]]]=f[y[i]],z[i]=3;  //  离线建图
    }
    num=0;
    for(int i=1;i<=n;i++) if(!fa[i]) dfs1(i);
    for(int i=1;i<=n;i++){if(!ord[i]) dfs2(i);upd(ord[i],a[i]);}  //  树剖预处理
    for(int i=1;i<=m;i++) if(!z[i]) printf("no\n");
    else if(z[i]==3) printf("yes\n");
    else if(z[i]==4) printf("impossible\n");
    else if(z[i]==1) upd(ord[x[i]],y[i]-sum(ord[x[i]])+sum(ord[x[i]]-1));  //  把 x 变为 y 相当于加 y-x
    else{
        int X=x[i],Y=y[i],s=0;
        while(top[X]!=top[Y]){
            if(dep[top[X]]<dep[top[Y]]) swap(X,Y);
            s+=sum(ord[X])-sum(ord[top[X]]-1),X=fa[top[X]];
        }
        if(ord[X]>ord[Y]) swap(X,Y);
        printf("%d\n",s+sum(ord[Y])-sum(ord[X]-1));
    }
    return 0;
}