「UNR#1」奇怪的线段树

一道好题,感觉解法非常自然。

首先我们只需要考虑一次染色最下面被包含的那些区间,因为把无解判掉以后只要染了一个节点,它的祖先也一定被染了。然后发现一次染色最下面的那些区间一定是一段连续的左儿子+一段连续的右儿子。

证明的话可以看官方题解,感性理解的话不难,同时,任意一段连续的左儿子+右儿子也对应一个区间。定义一个左儿子区间 \([l_i,r_i]\) 的后继是所有 \(r_i=l_i+1\) 的左儿子和右儿子,一个右儿子区间 \([l_i,r_i]\) 的后继是所有 \(r_i=l_i+1\) 的右儿子区间,不难发现这是一个DAG。那么这张图的一条路径就对应了原图的一个染色区间,也就是要求这个DAG的最小路径覆盖,优化建图+上下界最小流即可。

code

/*program by mangoyang*/
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int ch = 0, f = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 200005, M = 200005;
int L[N], R[N], col[N], low[N], isl[N], n, NS, NT, cnt = 1;
inline void init(int u, int l, int r){
L[u] = l, R[u] = r;
if(l == r)
return (void) (read(col[u]), low[u] = col[u]);
int mid, lc, rc;
read(col[u]), read(mid);
init(lc = ++cnt, l, mid), init(rc = ++cnt, mid + 1, r);
isl[lc] = 1;
if(!col[u] && (col[lc] || col[rc])){
puts("OwO"); exit(0);
}
low[u] = col[u] && (!col[lc]) && (!col[rc]);
}
namespace flow{
queue<int> q;
int a[M], cap[M], nxt[M], head[N], cur[N], dis[N], S, T, cnt = 1;
inline void addedge(int x, int y, int z){
a[++cnt] = y, cap[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
a[++cnt] = x, cap[cnt] = 0, nxt[cnt] = head[y], head[y] = cnt;
}
inline int bfs(){
memset(dis, -1, sizeof(dis)), dis[S] = 0, q.push(S);
for(; !q.empty(); q.pop()){
int u = q.front();
for(int p = head[u]; p; p = nxt[p]){
int v = a[p];
if(~dis[v] || !cap[p]) continue;
dis[v] = dis[u] + 1, q.push(v);
}
}
return ~dis[T];
}
inline int dfs(int u, int flow){
if(u == T || !flow) return flow;
int used = 0;
for(int &p = cur[u]; p; p = nxt[p]){
int v = a[p];
if(dis[v] != dis[u] + 1 || !cap[p]) continue;
int x = dfs(v, min(flow, cap[p]));
used += x, flow -= x, cap[p] -= x, cap[p^1] += x;
if(!flow) break;
}
return used;
}
inline void setflow(int x, int y){ S = x, T = y; }
inline int getflow(){
int res = 0;
for(; bfs(); res += dfs(S, inf))
memcpy(cur, head, sizeof(cur));
return res;
}
}
inline void addedge(int x, int y, int a, int b){
flow::addedge(NS, y, a);
flow::addedge(x, NT, a);
flow::addedge(x, y, b - a);
}
int main(){
read(n);
init(1, 1, n);
int S = n * 6 + 1, T = S + 1;
NS = T + 1, NT = NS + 1;
for(int i = 1; i < (n << 1); i++) if(col[i]){
addedge(i, i + (n << 1), low[i], inf);
addedge(L[i] + (n << 2), i, 0, inf);
addedge(i + (n << 1), T, 0, inf);
addedge(S, i, 0, inf);
if(isl[i]){
if(R[i] < n)
addedge(i + (n << 1), R[i] + 1 + (n << 2) + n, 0, inf);
addedge(L[i] + (n << 2) + n, i, 0, inf);
}
else if(R[i] < n)
addedge(i + (n << 1), R[i] + 1 + (n << 2), 0, inf);
}
flow::setflow(NS, NT);
flow::getflow();
flow::addedge(T, S, inf);
cout << flow::getflow() << endl;
return 0;
}
05-11 22:42