[CF487E] Tourists

题目链接

codeforces.

洛谷.

Solution

建圆方树，对于圆点权值直接就是点权，方点权值就是所有儿子的最小值，这个可以对于每个方点开一个\(multiset\)维护儿子点权。

那么直接上树剖就好了，注意如果\(lca\)是方点，那么他父亲的贡献也要算上。

复杂度\(O(n\log ^2n)\)。

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
#define iter multiset<int > :: iterator 

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;

int n,m,val[maxn],cnt,rev[maxn];
multiset<int > s[maxn];

struct Segment_Tree {
    int t[maxn];
    void update(int p) {t[p]=min(t[ls],t[rs]);}

    void build(int p,int l,int r) {
        if(l==r) return t[p]=val[rev[l]],void();
        build(ls,l,mid),build(rs,mid+1,r),update(p);
    }
    
    void modify(int p,int l,int r,int x,int v) {
        if(l==r) return t[p]=v,void();
        if(x<=mid) modify(ls,l,mid,x,v);
        else modify(rs,mid+1,r,x,v);
        update(p);
    }
    
    int query(int p,int l,int r,int x,int y) {
        if(x<=l&&r<=y) return t[p];
        int res=1e9;
        if(x<=mid) res=min(res,query(ls,l,mid,x,y));
        if(y>mid) res=min(res,query(rs,mid+1,r,x,y));
        return res;
    }
}SGT;

struct Heavy_Light_Decomposation {  
    int head[maxn],tot,dfn[maxn],dfn_cnt,top[maxn],sz[maxn],dep[maxn],hs[maxn],fa[maxn];
    struct edge{int to,nxt;}e[maxn<<1];

    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
    void ins(int u,int v) {add(u,v),add(v,u);}
    
    void dfs1(int x,int Fa) {
        fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;
        if(x>n) val[x]=*s[x].begin();
        for(int v,i=head[x];i;i=e[i].nxt) {
            if((v=e[i].to)==Fa) continue;
            dfs1(v,x),sz[x]+=sz[v];
            if(sz[hs[x]]<sz[v]) hs[x]=v;
        }
    }
    
    void dfs2(int x) {
        if(hs[fa[x]]==x) top[x]=top[fa[x]];
        else top[x]=x;dfn[x]=++dfn_cnt;rev[dfn[x]]=x;
        if(hs[x]) dfs2(hs[x]);
        for(int i=head[x];i;i=e[i].nxt)
            if(e[i].to!=fa[x]&&e[i].to!=hs[x]) dfs2(e[i].to);
    }
    
    void modify(int x,int c) {
        int v=fa[x];
        iter i=s[v].find(val[x]);
        if(v) s[v].erase(i),s[v].insert(c),val[v]=*s[v].begin();
        if(v) SGT.modify(1,1,cnt,dfn[v],val[v]);
        val[x]=c;
        SGT.modify(1,1,cnt,dfn[x],val[x]);
    }
    
    int query(int x,int y) {
        int ans=1e9;
        while(top[x]!=top[y]) {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans=min(ans,SGT.query(1,1,cnt,dfn[top[x]],dfn[x]));
            x=fa[top[x]];
        }if(dep[x]>dep[y]) swap(x,y);
        if(x>n) ans=min(ans,val[fa[x]]);
        ans=min(ans,SGT.query(1,1,cnt,dfn[x],dfn[y]));
        return ans;
    }
}T;

struct Graph {
    int head[maxn],tot,dfn[maxn],low[maxn],sta[maxn],top,dfn_cnt;
    struct edge{int to,nxt;}e[maxn<<1];

    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
    void ins(int u,int v) {add(u,v),add(v,u);}
    
    void tarjan(int x,int fa) {
        dfn[x]=low[x]=++dfn_cnt;sta[++top]=x;
        for(int v,i=head[x];i;i=e[i].nxt) {
            if((v=e[i].to)==fa) continue;
            if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);
            else {low[x]=min(low[x],dfn[v]);continue;}
            if(low[v]>=dfn[x]) {
                cnt++;T.ins(x,cnt);
                while(top) {
                    int now=sta[top--];T.ins(now,cnt);
                    s[cnt].insert(val[now]);
                    if(now==v) break;
                }val[cnt]=*s[cnt].begin();
            }
        }
    }
}G;

int main() {
    int q;read(n),read(m),read(q);
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1,x,y;i<=m;i++) read(x),read(y),G.ins(x,y);
    cnt=n;G.tarjan(1,0);T.dfs1(1,0),T.dfs2(1);SGT.build(1,1,cnt);
    for(int i=1;i<=q;i++) {
        int x,y;char s[5];
        scanf("%s",s+1);read(x),read(y);
        if(s[1]=='A') write(T.query(x,y));
        else T.modify(x,y);
    }
    return 0;
}

[CF487E] Tourists

原文：https://www.cnblogs.com/hbyer/p/10617781.html