P14528 [BYOI R1] 雨后屋檐 题解

Getaway_Car
  2025-11-16 18:30 2025-11-16 18:30 Creado   2025-12-14 18:23:10 2025-12-14 18:23:10 Actualizado      1.4k Palabras  7 Minutos  
题面 & 提示

P1318 加强版，区别在于本题包含多个询问，每个询问给定查询的区间 与最大水面高度 ，强制在线。P1318 的做法对本题有一些启发。

设 同阶。

考虑本题的难点在哪里。发现屋顶的两侧不一定足够高，所以一些水会流出去。

考虑特殊性质，此时没有水会流出去。考虑这时该怎么做。发现此时的答案为：

即：

发现这个问题相当于二维数点，于是考虑使用可持久化权值线段树解决，详见 P10814。

去掉特殊性质，容易发现，只要一个区间两侧的屋顶高度 ，就可以用上述方法解决。于是我们尝试从询问的区间 中找到一个两端高度都不小于 的子区间。

令 ，这对答案没有影响；令 表示区间左侧第一个满足 的位置 ；同理，令 表示区间右侧第一个满足 的位置 。计算 可以通过线段树二分解决。显然 一定存在。

此时问题被划分为了 、 与 三段。第二段是前文中已经讨论的情况，是容易算出水的体积的。一三段的问题是对称的，所以接下来讨论第一段。

接下来是 P1318 的结论。

设位置 的水面相对地面高度为 。特别地，若位置 没有水，则令 。容易注意到，，有：

注意到前者一定小于后者，于是我们就有了第一段的答案：

后者是容易维护的，考虑如何维护前者。前者是区间前缀最大值之和，即 P5648。直接使用 P5648 的做法即可。

直接把三段的答案加在一起就可以得到总答案。

时间复杂度 ，空间复杂度 ，有巨大常数。

一个常数优化

考虑优化计算 的过程。

按照 P5648 的做法，我们利用单调栈建了一棵树。注意到在向右连边的树中， 一定是 的父亲或其本身，所以可以通过树上倍增来计算 。

同理。

Code

我人傻常数大，跑得挺慢的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#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;
}
  • Título: P14528 [BYOI R1] 雨后屋檐 题解
  • Autor: Getaway_Car
  • Creado el : 2025-11-16 18:30:00
  • Actualizado el : 2025-12-14 18:23:10
  • Enlace: https://getawaycar1024.github.io/article/P14528-BYOI-R1-雨后屋檐-题解/
  • Licencia: Este trabajo está licenciado bajo CC BY-NC-SA 4.0.
Comentarios
En esta página
P14528 [BYOI R1] 雨后屋檐 题解