cf487E Tourists 圆方树+树链剖分

Solution

---

给定一个无向图，要求资磁
1. 询问两点间简单路径的并上的点权最小值
2. 修改点权

Solution

---

看到简单路径的并可以想到圆方树，要修改可以考虑树剖
最初的想法是方点记录所在连通分量的最小点权，但是这样修改就不好做了
看了题解才知道可以只记录圆儿子的点权，那么修改的时候就是一一对应的了，这个可以用支持插入删除求最值的multiset搞
需要注意的是当两个询问点的lca为方点时要多算一个方点的父亲

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <stack>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))

const int INF=0x3f3f3f3f;
const int N=400005;
const int E=800005;

std:: stack <int> stack;
std:: multiset <int> set[N];

struct Graph {
    struct edge {int y,next;} e[E];
    int ls[N],edCnt;
    void add_edge(int x,int y) {
        e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
        e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
    }
} G,T;

int min[N<<2],tot,n;
int dfn[N],low[N],w[N],dep[N];
int size[N],pos[N],bl[N],fa[N];

bool vis[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void tarjan(int now,int from) {
    dfn[now]=low[now]=++dfn[0]; vis[now]=1;
    for (int i=G.ls[now];i;i=G.e[i].next) {
        if (i==(from^1)) continue;
        if (!dfn[G.e[i].y]) {
            stack.push(i); tarjan(G.e[i].y,i);
            low[now]=std:: min(low[now],low[G.e[i].y]);
            if (dfn[now]<=low[G.e[i].y]) {
                int y=0; w[++ tot]=INF;
                while (y!=i) {
                    y=stack.top(); stack.pop();
                    T.add_edge(G.e[y].y,tot);
                }
                T.add_edge(now,tot);
            }
        } else if (vis[G.e[i].y]) low[now]=std:: min(low[now],dfn[G.e[i].y]);
    }
    vis[now]=0;
}

void dfs1(int now) {
    size[now]=1;
    for (int i=T.ls[now];i;i=T.e[i].next) {
        if (T.e[i].y==fa[now]) continue;
        fa[T.e[i].y]=now;
        dep[T.e[i].y]=dep[now]+1;
        dfs1(T.e[i].y);
        size[now]+=size[T.e[i].y];
    }
}

void dfs2(int now,int up) {
    int mx=0; pos[now]=++pos[0]; bl[now]=up;
    for (int i=T.ls[now];i;i=T.e[i].next) {
        if (T.e[i].y!=fa[now]&&size[T.e[i].y]>size[mx]) mx=T.e[i].y;
    }
    if (!mx) return ;
    dfs2(mx,up);
    for (int i=T.ls[now];i;i=T.e[i].next) {
        if (T.e[i].y!=fa[now]&&T.e[i].y!=mx) dfs2(T.e[i].y,T.e[i].y);
    }
}

void modify(int now,int tl,int tr,int x,int v) {
    if (tl==tr) return (void) (min[now]=v);
    int mid=(tl+tr)>>1;
    if (x<=mid) modify(now<<1,tl,mid,x,v);
    else modify(now<<1|1,mid+1,tr,x,v);
    min[now]=std:: min(min[now<<1],min[now<<1|1]);
}

int query(int now,int tl,int tr,int l,int r) {
    if (tl==l&&tr==r) return min[now];
    int mid=(tl+tr)>>1;
    if (r<=mid) return query(now<<1,tl,mid,l,r);
    if (l>mid) return query(now<<1|1,mid+1,tr,l,r);
    int qx=query(now<<1,tl,mid,l,mid);
    int qy=query(now<<1|1,mid+1,tr,mid+1,r);
    return std:: min(qx,qy);
}

void solve(int x,int y) {
    int ans=INF;
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) std:: swap(x,y);
        int ret=query(1,1,pos[0],pos[bl[x]],pos[x]);
        ans=std:: min(ret,ans);
        x=fa[bl[x]];
    }
    if (pos[x]>pos[y]) std:: swap(x,y);
    ans=std:: min(ans,query(1,1,pos[0],pos[x],pos[y]));
    if (x>n) ans=std:: min(ans,w[fa[x]]);
    printf("%d\n", ans);
}

int main(void) {
    G.edCnt=1;
    n=read(); int m=read(),q=read();
    rep(i,1,n) w[i]=read();
    rep(i,1,m) {
        int x=read(),y=read();
        G.add_edge(x,y);
    } tot=n;
    tarjan(1,-1);
    dep[1]=1; dfs1(1); dfs2(1,1);
    rep(now,n+1,tot) {
        for (int i=T.ls[now];i;i=T.e[i].next) {
            if (T.e[i].y==fa[now]) continue;
            set[now].insert(w[T.e[i].y]);
        }
        w[now]=*set[now].begin();
    }
    rep(i,1,tot) modify(1,1,pos[0],pos[i],w[i]);
    for (;q--;) {
        char ch=getchar(); for (;ch!='A'&&ch!='C';ch=getchar());
        int x=read(),y=read();
        if (ch=='A') solve(x,y);
        else {
            if (fa[x]) set[fa[x]].erase(w[x]);
            w[x]=y; modify(1,1,pos[0],pos[x],y);
            if (fa[x]) {
                set[fa[x]].insert(w[x]);
                w[fa[x]]=*set[fa[x]].begin();
                modify(1,1,pos[0],pos[fa[x]],w[fa[x]]);
            }
        }
    }
    return 0;
}