【Codeforce 487E】【UOJ#30】—Tourists（圆方树+树链剖分）
题意：求无向图2点之间简单路径最小值
直接对无向图建出圆方树后树链剖分，
每个方点维护一下儿子最小值
用可删堆维护一下就好了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int RLEN=1<<18|1;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=gc();}
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return res*f;
}
const int N=400005;
const int inf=1e9;
int n,m,q,val[N],dfn[N],low[N],tot;
int fa[N],siz[N],son[N],dep[N],top[N],bel,pos[N],idx[N];
struct Graph{
int cnt,adj[N],nxt[N],to[N];
inline void addedge(int u,int v){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
nxt[++cnt]=adj[v],adj[v]=cnt,to[cnt]=u;
}
}G,T;
struct Heap{
priority_queue<int,vector<int>,greater<int> > A,B;
inline void push(int x){
A.push(x);
}
inline void pop(int x){
B.push(x);
}
inline int top(){
while(B.size()&&A.top()==B.top())
A.pop(),B.pop();
return A.top();
}
}p[N];
int S[N];
void tarjan(int u){
dfn[u]=low[u]=++tot;S[++S[0]]=u;
for (int e=G.adj[u];e;e=G.nxt[e]){
int v=G.to[e];
if (!dfn[v]){
tarjan(v),low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u]){
T.addedge(++bel,u);int x=0;
do{
x=S[S[0]--];T.addedge(bel,x);
}while (x!=v);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
namespace Seg{
int tr[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
void pushup(int u){
tr[u]=min(tr[lc],tr[rc]);
}
void build(int u,int l,int r){
if(l==r){
if(idx[l]<=n)tr[u]=val[idx[l]];
else tr[u]=p[idx[l]].top();
return;
}
build(lc,l,mid),build(rc,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int p,int k){
if(l==r)return tr[u]=k,void();
if(p<=mid)update(lc,l,mid,p,k);
else update(rc,mid+1,r,p,k);
pushup(u);
}
int query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des)return tr[u];
int res=inf;
if(st<=mid)res=min(res,query(lc,l,mid,st,des));
if(mid<des)res=min(res,query(rc,mid+1,r,st,des));
return res;
}
}
using namespace Seg;
void dfs1(int u){
siz[u]=1;
if(u<=n&&fa[u])p[fa[u]].push(val[u]);
for(int e=T.adj[u];e;e=T.nxt[e]){
int v=T.to[e];
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
pos[u]=++tot,top[u]=tp,idx[tot]=u;
if(son[u])dfs2(son[u],tp);
for(int e=T.adj[u];e;e=T.nxt[e]){
int v=T.to[e];
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
inline int pathquery(int u,int v){
int res=1e9;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
res=min(res,query(1,1,tot,pos[top[u]],pos[u]));
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
res=min(res,query(1,1,tot,pos[v],pos[u]));
if(v>n)res=min(res,val[fa[v]]);return res;
}
char op[5];
int main(){
bel=n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)val[i]=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
G.addedge(u,v);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);tot=0,dfs1(1),dfs2(1,1);
build(1,1,tot);
while(q--){
scanf("%s",op);
if(op[0]=='C'){
int u=read(),k=read();
if(fa[u])p[fa[u]].pop(val[u]);
val[u]=k,update(1,1,tot,pos[u],val[u]);
if(fa[u])p[fa[u]].push(val[u]),update(1,1,tot,pos[fa[u]],p[fa[u]].top());
}
else{
int u=read(),v=read();
cout<<pathquery(u,v)<<'\n';
}
}
}
1、Modern Operating System --- Chap 5.5.2 Clock Software
2、3.1 scrapy框架 -- Spider详解
3、Atitit.index manager api design 索引管理api设计
4、问个问题，希望讨论一下
5、Win32/MFC/COM学习推荐书籍