LOJ6032.「雅礼集训 2017 Day2」水箱

LOJ6032.「雅礼集训 2017 Day2」水箱

解题思路

不难想到将所有的条件按高度排序，本想从上向下建笛卡尔树但发现没有从下到上并查集合并更简便

每个节点维护 (res[x],cnt[x], f[x],L[x],R[x]) 这些数组，分别表示水淹到之前的最高高度或以下的最大答案，联通块里有多少条件要求被淹，并查集爸爸，联通块左端点和右端点

如果当前条件要求被淹，(res[x] = max(res[x], cnt[x] + 1))，否则直接 (res[x]++)

同时排序时如果高度相同，不被淹的条件要在被淹的前面，否则会计重

带码

const int N = 100500;
struct node {
	int x, y, z;
	bool operator < (const node &i) const {
		if (y != i.y) return y < i.y;
		return z < i.z;
	}
}q[N];

const int inf = 1e9;
int res[N], cnt[N], L[N], R[N], f[N], hi[N], T, m, n;
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void work(void) {
	read(n), read(m); cnt[n] = res[n] = 0;
	hi[0] = hi[L[n] = R[n] = f[n] = n] = inf;
	for (int i = 1; i < n; i++) 
		read(hi[L[i] = R[i] = f[i] = i]), res[i] = cnt[i] = 0;
	for (int i = 1;i <= m; i++)
		read(q[i].x), read(q[i].y), read(q[i].z);
	sort(q + 1, q + m + 1);
	for (int i = 1;i <= m; i++) {
		int x = find(q[i].x);
		while (hi[L[x]-1] <= q[i].y) {
			int y = find(L[x]-1); L[x] = L[y];
			cnt[x] += cnt[y], res[f[y] = x] += res[y];
		}
		while (hi[R[x]] <= q[i].y) {
			int y = find(R[x]+1); R[x] = R[y];
			cnt[x] += cnt[y], res[f[y] = x] += res[y];
		}
		if (q[i].z == 0) res[x]++;
		else cnt[x]++, Mx(res[x], cnt[x]);
	}
	ll ans = 0;
	for (int i = 1;i <= n; i++) if (find(i) == i) ans += res[i];
	write(ans);
}

int main() {
	for (read(T); T; T--) work();
	return 0;
}