专栏文章

P14528 [BYOI R1] 雨后屋檐 题解

GGetaway_Car
P14528题解参与者 2已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miopzt6a
此快照首次捕获于
2025/12/02 23:15
3 个月前
此快照最后确认于
2025/12/02 23:15
3 个月前
查看原文
题面 & 提示
P1318 加强版，区别在于本题包含多个询问，每个询问给定查询的区间 [l,r][l, r] 与最大水面高度 HH，强制在线。P1318 的做法对本题有一些启发。
设 n,qn, q 同阶。
考虑本题的难点在哪里。发现屋顶的两侧不一定足够高，所以一些水会流出去。
考虑特殊性质，此时没有水会流出去。考虑这时该怎么做。发现此时的答案为：
∑i=lrmax⁡(H−hi,0)\sum_{i = l}^r \max(H - h_i, 0)
即：
∑l≤i≤r,hi≤HH−hi\sum_{l \le i \le r, h_i \le H} H - h_i
发现这个问题相当于二维数点，于是考虑使用可持久化权值线段树解决，详见 P10814。
去掉特殊性质，容易发现，只要一个区间两侧的屋顶高度 ≥H\ge H，就可以用上述方法解决。于是我们尝试从询问的区间 [l,r][l, r] 中找到一个两端高度都不小于 HH 的子区间。
令 H←min⁡(max⁡i=lr{hi},H)H \leftarrow \min(\max_{i = l}^r \{h_i\}, H)，这对答案没有影响；令 LL 表示区间左侧第一个满足 hi≥Hh_i \ge H 的位置 ii；同理，令 RR 表示区间右侧第一个满足 hi≥Hh_i \ge H 的位置 ii。计算 L,RL, R 可以通过线段树二分解决。显然 L,RL, R 一定存在。
此时问题被划分为了 [l,L)[l, L)、[L,R][L, R] 与 (R,r](R, r] 三段。第二段是前文中已经讨论的情况，是容易算出水的体积的。一三段的问题是对称的，所以接下来讨论第一段。
接下来是 P1318 的结论。
设位置 ii 的水面相对地面高度为 aia_i。特别地，若位置 ii 没有水，则令 ai=hia_i = h_i。容易注意到，∀i∈[l,L)\forall i \in [l, L)，有：
ai=min⁡(max⁡j=li{hj},H)a_i = \min(\max_{j = l}^i\{h_j\}, H)
注意到前者一定小于后者，于是我们就有了第一段的答案：
∑i=lL−1max⁡j=li{hj}−∑i=lL−1hi\sum_{i = l}^{L - 1} \max_{j = l}^i \{h_j\} - \sum_{i = l}^{L - 1} h_i
后者是容易维护的，考虑如何维护前者。前者是区间前缀最大值之和，即 P5648。直接使用 P5648 的做法即可。
直接把三段的答案加在一起就可以得到总答案。
时间复杂度 O(nlog⁡n)O(n \log n)，空间复杂度 O(nlog⁡n)O(n \log n)，有巨大常数。
一个常数优化
考虑优化计算 LL 的过程。
按照 P5648 的做法，我们利用单调栈建了一棵树。注意到在向右连边的树中，LL 一定是 ll 的父亲或其本身，所以可以通过树上倍增来计算 LL。
RR 同理。
Code
我人傻常数大，跑得挺慢的。
CPP
#include <bits/stdc++.h>

#define rep(i, s, e) for(int i = s; i <= e; ++i)
#define _rep(i, s, e) for(int i = s; i >= e; --i)

#define uint unsigned int
#define uint64 unsigned long long

using namespace std;

const uint N = 500000;

template <typename T>
inline void read(T &x) {
	uint neg = 1; char ch;
	while (ch = getchar(), !isdigit(ch)) if (ch == '-') neg = -1;
	x = ch - '0';
	while (ch = getchar(), isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ '0');
	x *= neg;
}

template <typename T>
inline void write(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

// 可持久化权值线段树 
struct Segtree {
	uint rt[N + 5], ls[N << 5], rs[N << 5], cnt[N << 5], cntnode = 0;
	uint64 sum[N << 5];
	void build(uint l, uint r, uint &p) {
		if (!p) p = ++cntnode;
		sum[p] = 0;
		if (l == r) return;
		uint mid = (l + r) >> 1;
		build(l, mid, ls[p]);
		build(mid + 1, r, rs[p]);
	}
	void insert(uint l, uint r, uint &p, uint rt, uint s, uint d) {
		if (!p) p = ++cntnode;
		sum[p] = sum[rt] + d;
		cnt[p] = cnt[rt] + 1;
		if (l == r) return;
		uint mid = (l + r) >> 1;
		if (s <= mid) {
			insert(l, mid, ls[p], ls[rt], s, d);
			rs[p] = rs[rt];
		} else {
			insert(mid + 1, r, rs[p], rs[rt], s, d);
			ls[p] = ls[rt];
		}
	}
	pair<uint64, uint> query(uint l, uint r, uint p, uint s, uint t) {
		if (s > t) return {0ull, 0};
		if (s <= l && r <= t) return {sum[p], cnt[p]};
		uint mid = (l + r) >> 1, ans2 = 0;
		uint64 ans1 = 0;
		pair<uint64, uint> tmp;
		if (s <= mid) tmp = query(l, mid, ls[p], s, t), ans1 += tmp.first, ans2 += tmp.second;
		if (t > mid)  tmp = query(mid + 1, r, rs[p], s, t), ans1 += tmp.first, ans2 += tmp.second;
		return {ans1, ans2};
	}
} tr;

uint n, q, t, h[N + 5], to[N + 5], stk[N + 5], l, r, H, L, R, tp, tmp, lfa[N + 5][20], rfa[N + 5][20];
uint64 xl, xr, xH, ans, xorans, s[N + 5], ldep[N + 5], rdep[N + 5];
pair<uint64, uint> tmp1, tmp2;

signed main() {
	read(n), read(q), read(t);
	rep(i, 1, n) {
		read(h[i]);
		to[i] = h[i];
		s[i] = s[i - 1] + h[i];
	}
	sort(to + 1, to + n + 1);
	// 建可持久化权值线段树 
	tr.build(1, n, tr.rt[0]);
	rep(i, 1, n) {
		uint pos = lower_bound(to + 1, to + n + 1, h[i]) - to;
		tr.insert(1, n, tr.rt[i], tr.rt[i - 1], pos, h[i]);
	}
	h[0] = h[n + 1] = 1e9 + 7;
	// 建向右的树 
	tp = 0;
	rep(i, 1, n + 1) {
		while(tp and h[stk[tp]] < h[i]) {
			rfa[stk[tp--]][0] = i;
		}
		stk[++tp] = i;
	}
	_rep(i, n, 1) {
		rdep[i] = rdep[rfa[i][0]]; 
		rdep[i] += 1ull * h[i] * (rfa[i][0] - i - 1);
		rdep[i] -= (s[rfa[i][0] - 1] - s[i]);
	}
	rfa[n + 1][0] = n + 1;
	rep(j, 1, 19) {
		rep(i, 1, n) {
			rfa[i][j] = rfa[rfa[i][j - 1]][j - 1];
		}
	}
	// 建向左的树 
	tp = 0;
	_rep(i, n, 0) {
		while(tp and h[stk[tp]] < h[i]) {
			lfa[stk[tp--]][0] = i;
		}
		stk[++tp] = i;
	}
	rep(i, 1, n) {
		ldep[i] = ldep[lfa[i][0]];
		ldep[i] += 1ull * h[i] * (i - lfa[i][0] - 1);
		ldep[i] -= (s[i - 1] - s[lfa[i][0]]);
	}
	lfa[0][0] = 0;
	rep(j, 1, 19) {
		rep(i, 1, n) {
			lfa[i][j] = lfa[lfa[i][j - 1]][j - 1];
		}
	}
	while (q--) {
		read(xl), read(xr), read(xH);
		if(!t) ans = 0;
		l = xl ^ ans, r = xr ^ ans, H = xH ^ ans;
		ans = 0;
		if(h[L = l] < H) {
			// 倍增求 L
			_rep(i, 19, 0) {
				if(rfa[L][i] <= r and h[rfa[L][i]] < H) {
					L = rfa[L][i];
				}
			}
			if(rfa[L][0] <= r) L = rfa[L][0];
		}
		R = r;
		if(h[R = r] < H) {
			// 倍增求 R
			_rep(i, 19, 0) {
				if(lfa[R][i] >= l and h[lfa[R][i]] < H) {
					R = lfa[R][i];
				}
			}
			if(lfa[R][0] >= l) R = lfa[R][0];
		}
		H = min(H, max(h[L], h[R]));
		// 处理 [L, R] 
		if (L + 1 <= R - 1) {
			tmp = upper_bound(to + 1, to + n + 1, H) - to - 1;
			tmp1 = tr.query(1, n, tr.rt[R - 1], 1, tmp);
			tmp2 = tr.query(1, n, tr.rt[L], 1, tmp);
			ans += 1ull * (tmp1.second - tmp2.second) * H;
			ans -= tmp1.first - tmp2.first;
		}
		if (l <= L) ans += rdep[l] - rdep[L]; // 处理 [l, L)
		if (R <= r) ans += ldep[r] - ldep[R]; // 处理 (r, R]
		xorans ^= ans;
	}
	write(xorans);
	return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...