「UNR#1」奇怪的线段树

「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;

}