…
- 学习了一波圆方树
- 学习了一波点分治
- 学习了一波可删除堆(巧用 ? STL)
传送门: Icefox_zhx
注意看代码看怎么构建圆方树的.
tips:tips:tips:圆方树内存记得开两倍
CODE
#include <vector>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
inline void read(int &num) {
char ch; int flg=1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;
for(num=0; isdigit(ch); num=num*10+ch-'0',ch=getchar()); num*=flg;
}
const int MAXN = 100005;
const int INF = 1e9;
int n, m, q, tot, w[MAXN], dfn[MAXN<<1], tmr, stk[MAXN], indx;
vector<int> e[MAXN];
struct Heap {
priority_queue<int, vector<int>, greater<int> >A, B;
inline void insert(int x) { A.push(x); }
inline void erase(int x) { B.push(x); }
inline int top() {
while(!B.empty() && A.top() == B.top()) A.pop(), B.pop();
return A.empty() ? INF : A.top();
}
}W[MAXN];
int fir[MAXN<<1], to[MAXN<<2], nxt[MAXN<<2], cnt;
inline void add(int u, int v) {
to[cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt++;
}
int tarjan(int u, int fa) {
int lowu = dfn[u] = ++tmr;
stk[++indx] = u;
for(int v, lowv, i = 0, siz = e[u].size(); i < siz; ++i)
if(!dfn[v=e[u][i]]) {
lowu = min(lowu, lowv=tarjan(v, u));
if(lowv >= dfn[u]) {
fir[++tot] = -1;
do {
W[tot-n].insert(w[stk[indx]]), add(tot, stk[indx]);
}while(stk[indx--] != v);
add(u, tot);
}
}
else if(v != fa) lowu = min(lowu, dfn[v]);
return lowu;
}
int dep[MAXN<<1], fa[MAXN<<1], sz[MAXN<<1], top[MAXN<<1], son[MAXN<<1], seq[MAXN<<1];
void dfs(int u, int ff) {
dep[u] = dep[fa[u]=ff] + (sz[u]=1);
for(int v, i = fir[u]; ~i; i = nxt[i]) {
dfs(v=to[i], u), sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp; seq[dfn[u] = ++tmr] = u;
if(son[u]) dfs2(son[u], tp);
for(int v, i = fir[u]; ~i; i = nxt[i])
if((v=to[i]) != son[u]) dfs2(v, v);
}
int mn[MAXN<<3];
inline void upd(int i) { mn[i] = min(mn[i<<1], mn[i<<1|1]); }
void build(int i, int l, int r) {
if(l == r) { mn[i] = seq[l] <= n ? w[seq[l]] : W[seq[l]-n].top(); return; }
int mid = (l + r) >> 1;
build(i<<1, l, mid);
build(i<<1|1, mid+1, r);
upd(i);
}
void modify(int i, int l, int r, int x) {
if(l == r) { mn[i] = seq[l] <= n ? w[seq[l]] : W[seq[l]-n].top(); return; }
int mid = (l + r) >> 1;
if(x <= mid) modify(i<<1, l, mid, x);
else modify(i<<1|1, mid+1, r, x);
upd(i);
}
int query(int i, int l, int r, int x, int y) {
if(l == x && r == y) return mn[i];
int mid = (l + r) >> 1;
if(y <= mid) return query(i<<1, l, mid, x, y);
else if(x > mid) return query(i<<1|1, mid+1, r, x, y);
else return min(query(i<<1, l, mid, x, mid), query(i<<1|1, mid+1, r, mid+1, y));
}
inline int Min(int x, int y) {
int res = INF;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res = min(res, query(1, 1, tot, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if(dfn[x] < dfn[y]) swap(x, y);
res = min(res, query(1, 1, tot, dfn[y], dfn[x]));
if(y > n) res = min(res, w[fa[y]]);
return res;
}
int main() {
read(n), read(m), read(q); tot = n;
for(int i = 1; i <= n; ++i) fir[i] = -1, read(w[i]);
for(int i = 1, x, y; i <= m; ++i)
read(x), read(y), e[x].push_back(y), e[y].push_back(x);
tarjan(1, 0); tmr = 0; dfs(1, 0); dfs2(1, 1);
build(1, 1, tot);
char s; int x, y;
while(q--) {
while(!isalpha(s=getchar()));
read(x), read(y);
if(s == 'C') {
if(fa[x]) {
W[fa[x]-n].erase(w[x]);
W[fa[x]-n].insert(y);
modify(1, 1, tot, dfn[fa[x]]);
}
w[x] = y;
modify(1, 1, tot, dfn[x]);
}
else printf("%d\n", Min(x, y));
}
}