如果不是uoj上有的话(听说这是China Round),我有可能就错过这道题目了(这是我有史以来为oi写的最长的代码,用了我一天TAT!)。
题目
传送门。
一个连通无向图,点上有权,支持两种操作:
- 修改某点的权值
- 询问点\(x\)到\(y\)的经过的最小的点(同一个点不能重复经过)
算法
这题想起来是不难的:
容易想到做一个强连通分量,每个分量里的点可以互相到达。
这时会有一个猜想:在一个分量里,是不是任意指定三点\(a,b,c\),都有一条合法路径从\(a\)到\(b\)途中经过\(c\)呢。我当时想了想,也没严谨证明,觉得是对的,现在做完了觉得有必要证明一下,然后我就在解答里找到了这个:
这个证明不走寻常路,通过最小割来证明,服了!
这样子我们就可以将每个分量看作一个点生成一棵树,询问只需要做一个LCA,修改就用一个堆维护。因为有修改操作,所以就把LCA改为树链剖分。
问题在于,一点可能在许多个分量里,那么修改时需要修改很多堆,于是,可以把每个割点的值仅仅维护在它的父亲分量(这是相对于深度优先搜索树而言),不过这样询问时要记得特殊处理LCA的值,就是说它们的LCA有一个割点的信息在它们LCA的父亲上。构图类似下面的。
注:右边的每个点都是一个分量,并且里面的信息用堆维护。这里的连线是对应的点。点的颜色表示,左边某色的所有点的信息储存在右边相同颜色的点上。
也许你已经注意到了,有一个特殊地方,如果\(a\)和\(b\)相连,那么这里可以就把它们当作一个分量。并且为了写程序方便,故意在根结点的顶部多加了一个点。
代码
有两个很坑的地方(对于我来说):
- 不要用set而是multiset
- dfs子结点\(u\)后,不要漏了这一句(太久没写tarjan了):
low[v] = min(low[v], low[u])
。
5.4k(已经过滤掉了0.8k的调试信息)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
template <class t>
void tension(t &a, const t &b) {
if (b < a) {
a = b;
}
}
template <class t>
void relax(t &a, const t &b) {
if (b > a) {
a = b;
}
}
const int INF = 0x3f3f3f3f;
const int MAXN = (int) 1e5 + 3;
const int MAXM = (int) 1e5 + 3;
const int MAXSIZE = 1 << 19;
int n, m, Q, A[MAXN];
struct Edge {
int to;
Edge *next;
};
struct BCC {
multiset<int> s;
void insert(int);
int maxval;
BCC() {
maxval = INF;
}
void change(int a, int b) {
s.erase(s.find(a));
s.insert(b);
maxval = *s.begin();
}
};
int cntBcc;
BCC bcc[MAXN * 2];
int idxNew[MAXN];
void BCC::insert(int x) {
s.insert(A[x]);
maxval = *s.begin();
}
namespace zkwSegmentTree {
int depth;
int A[MAXSIZE + 1];
void init(int size) {
while ((1 << depth) - 2 < size) {
depth ++;
}
}
void initModify(int x, int v) {
A[(1 << depth) + x] = v;
}
void upgrade() {
for (int i = (1 << depth) - 1; i; i --)
A[i] = min(A[i << 1], A[i << 1 ^ 1]);
}
int query(int a, int b) {
a = (1 << depth) + a - 1;
b = (1 << depth) + b + 1;
int ans = INF;
for (; a ^ b ^ 1; a >>= 1, b >>= 1) {
if (~a & 1) tension(ans, A[a ^ 1]);
if ( b & 1) tension(ans, A[b ^ 1]);
}
return ans;
}
void modify(int a, int v)
{
a = (1 << depth) + a;
A[a] = v;
for (a >>= 1; a; a >>= 1)
A[a] = min(A[a << 1], A[a << 1 ^ 1]);
}
}
namespace newGraph {
const int MAXNODE = MAXN * 2;
int root;
Edge *info[MAXNODE], mem[MAXNODE], *cur_mem = mem;
int fa[MAXNODE];
void insert(int f, int s) {
cur_mem->to = s;
cur_mem->next = info[f];
info[f] = cur_mem ++;
}
int cntPath;
int top[MAXNODE], heavySon[MAXNODE];
int dep[MAXNODE], size[MAXNODE], belong[MAXNODE];
int idxMap[MAXNODE];
int cutVertex[MAXNODE];
void cutLightHeavy() {
static int que[MAXNODE];
int low = 0, high = 0;
que[high ++] = root;
fa[root] = -1;
while (low < high) {
int v = que[low ++];
for (Edge *pt = info[v]; pt; pt = pt->next) {
int u = pt->to;
que[high ++] = u;
dep[u] = dep[v] + 1;
fa[u] = v;
}
}
for (int i = high - 1; i >= 0; i --) {
int v = que[i];
size[v] = 1;
heavySon[v] = -1;
for (Edge *pt = info[v]; pt; pt = pt->next) {
int u = pt->to;
size[v] += size[u];
if (heavySon[v] == -1 || size[u] > size[heavySon[v]]) {
heavySon[v] = u;
}
}
}
zkwSegmentTree::init(cntBcc);
int cntIdx = 1;
for (int i = 0; i < high; i ++) {
int v = que[i];
if (idxMap[v] == 0) {
top[cntPath] = v;
for (; v != -1; v = heavySon[v]) {
idxMap[v] = cntIdx ++;
zkwSegmentTree::initModify(idxMap[v], bcc[v].maxval);
belong[v] = cntPath;
}
cntPath ++;
}
}
zkwSegmentTree::upgrade();
}
int query(int a, int b) {
int ret = INF;
a = idxNew[a], b = idxNew[b];
while (belong[a] != belong[b]) {
if (dep[top[belong[a]]] < dep[top[belong[b]]]) {
swap(a, b);
}
tension(ret, zkwSegmentTree::query(idxMap[top[belong[a]]], idxMap[a]));
a = fa[top[belong[a]]];
}
if (dep[a] < dep[b]) swap(a, b);
tension(ret, zkwSegmentTree::query(idxMap[b], idxMap[a]));
tension(ret, A[cutVertex[b]]);
return ret;
}
}
namespace srcGraph {
Edge *info[MAXN], mem[MAXM * 2], *cur_mem = mem;
void insert2(int a, int b) {
cur_mem->to = b;
cur_mem->next = info[a];
info[a] = cur_mem ++;
cur_mem->to = a;
cur_mem->next = info[b];
info[b] = cur_mem ++;
}
void init() {
for (int i = 0; i < m; i ++) {
int a, b;
scanf("%d%d\n", &a, &b);
insert2(a, b);
}
}
int dfn[MAXN], low[MAXN], bccFa[MAXN];
void make() {
stack< pair<int, Edge*> > stk;
stk.push(make_pair(1, (Edge*) NULL) );
stack<int> contain;
memset(dfn, -1, sizeof(dfn));
memset(low, -1, sizeof(low));
memset(bccFa, -1, sizeof(bccFa));
int cntDfn = 0;
while (! stk.empty()) {
int v = stk.top().first;
Edge *&pt = stk.top().second;
if (! pt) {
dfn[v] = low[v] = cntDfn ++;
pt = info[v];
contain.push(v);
}
else {
int u = pt->to;
tension(low[v], low[u]);
if (low[u] == dfn[v]) {
int newBcc = cntBcc ++;
while (true) {
int t = contain.top();
if (bccFa[t]) {
newGraph::insert(newBcc, bccFa[t]);
}
bcc[newBcc].insert(t);
if (bccFa[t] == -1) idxNew[t] = newBcc;
contain.pop();
if (t == u) break;
}
if (bccFa[v] == -1) {
idxNew[v] = cntBcc;
bccFa[v] = cntBcc ++;
newGraph::cutVertex[bccFa[v]] = v;
}
newGraph::cutVertex[newBcc] = v;
newGraph::insert(bccFa[v], newBcc);
}
}
for (; pt; pt = pt->next) {
int u = pt->to;
if (dfn[u] != -1) tension(low[v], dfn[u]);
else {
stk.push(make_pair(u, (Edge*) NULL));
break;
}
}
if (! pt) stk.pop();
}
newGraph::root = bccFa[1];
idxNew[1] = bccFa[1];
}
}
int main() {
scanf("%d%d%d\n", &n, &m, &Q);
for (int i = 1; i <= n; i ++) {
scanf("%d\n", A + i);
}
srcGraph::init();
srcGraph::make();
newGraph::cutLightHeavy();
for (int i = 0; i < Q; i ++) {
char opt;
int a, b;
scanf("%c%d%d\n", &opt, &a, &b);
if (opt == 'A') {
int ans = a == b ? A[a] : newGraph::query(a, b);
printf("%d\n", ans);
}
else {
int t = idxNew[a];
if (t == newGraph::root) {
A[a] = b;
continue;
}
if (srcGraph::bccFa[a] != -1) {
t = newGraph::fa[t];
}
bcc[t].change(A[a], b);
A[a] = b;
zkwSegmentTree::modify(newGraph::idxMap[t], bcc[t].maxval);
}
}
return 0;
}