洛谷 P7922 [Kubic] Pyramid 题解

题解/做题记录
16k 词

洛谷 P7922 [Kubic] Pyramid 题解

题目链接

给定一个初始长度为 nn 的序列 pp。

设当前 pp 的长度为 LL，有以下两种操作：

  • A 操作先构造长度为 L−1L-1 的序列 p′p' 满足 pi′=min⁡{pi,pi+1},i∈[1,L)p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)。然后用 p′p' 代替 pp。

  • B 操作先构造长度为 L−1L-1 的序列 p′p' 满足 pi′=max⁡{pi,pi+1},i∈[1,L)p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)。然后用 p′p' 代替 pp。

再给定一个长度为 mm 的序列 aa，表示一共进行 mm 组操作，第 ii 组中先进行 aia_i 次 A 操作，再进行 aia_i 次 B 操作。保证 2∑ai=n−12\sum a_i=n-1。

最后给定 qq 次询问，每次给出参数 x,l,rx,l,r，你需要求出进行前 xx 个操作之后 ∑i=lrpi\sum\limits_{i=l}^r p_i 的值。

注意：询问中的 xx 指的是前 xx 个操作而不是前 xx 组操作，即有可能在某一组操作进行一部分时询问。

Subtask 1

暴力按题意模拟即可。

Subtask 2

考虑连续的四个数 a,b,c,da, b, c, d，在两次操作后会留下两个数。

分讨 a,b,ca, b, c 的大小关系：

  • 若 a>b,b<ca > b, b < c，则一次操作后剩下 b,b,min⁡{c,d}b, b, \min\{c, d\}，两次操作后剩下 b,max⁡{b,min⁡{c,d}}b, \max\{b, \min\{c, d\}\}。
  • 若 a<b<ca < b < c，则一次操作后剩下 a,b,min⁡{c,d}a, b, \min\{c, d\}，两次操作后剩下 b,max⁡{b,min⁡{c,d}}b, \max\{b, \min\{c, d\}\}。
  • 若 a>b>ca > b > c，则一次操作后剩下 b,c,min⁡{c,d}b, c, \min\{c, d\}，两次操作后剩下 b,max⁡{c,min⁡{c,d}}b, \max\{c, \min\{c, d\}\}，即 b,cb, c。
  • 若 a<b,b>ca < b, b > c，则一次操作后剩下 a,c,min⁡{c,d}a, c, \min\{c, d\}，两次操作后剩下 max⁡{a,c},max⁡{c,min⁡{c,d}}\max\{a, c\}, \max\{c, \min\{c, d\}\}，即 max⁡{a,c},c\max\{a, c\}, c。

可以发现所有情况都会留下 min⁡{b,c}\min\{b, c\} 和一个大于 min⁡{b,c}\min\{b, c\} 的数，因此扩展到长度为 2k2k 的序列后，经过 2k−22k - 2 次操作剩下的两个数一定是中间两个数的最小值和一个比它大的数，因此最后留下的就是中间两个数的最小值。

则当 xx 为奇数时，答案为 min⁡{pl+⌊x2⌋,pl+⌈x2⌉}\min\{p_{l + \lfloor\frac{x}{2}\rfloor}, p_{l + \lceil\frac{x}{2}\rceil}\}；当 xx 为偶数时，手动模拟第一步即可转化为 xx​ 为奇数的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace Subtask2 {
	int pp[150005];

	void main() {
		for (int i = 1; i < n; i++) pp[i] = min(p[i], p[i + 1]);
		while (q--) {
			int x, l, r;
			scanf("%d%d%d", &x, &l, &r);
			if (x % 2) printf("%d\n", min(p[l + x / 2], p[l + x / 2 + 1]));
			else printf("%d\n", max(pp[l + x / 2 - 1], pp[l + x / 2]));
		}
		return ;
	}
}

Subtask 3

先考虑 a1≥ai(i∈(1,m])a_1 \ge a_i (i \in (1, m]) 的情况。

考虑 01 序列。先把前 2a12a_1 次操作做掉，在做前 a1a_1 次操作时，每次操作每个不在首尾的极长的 00 连续段长度都会增加至少 11，因此做完前 a1a_1 次操作后，所有不在首尾的极长的 00 连续段的长度都至少为 a1+1a_1 + 1。同理，做完后 a1a_1 次操作后，所有不在首尾的极长的 11 连续段的长度都至少为 a1+1a_1 + 1。由于 ai≤a1a_i \le a_1，且每次都是先做 aia_i 次 A 操作再做 aia_i 次 B 操作，因此之后的操作都不会出现合并两个连续段的情况。

然后分析之后的每个 aia_i，发现对于不在首尾的极长连续段，其长度变化量为 00，而首尾的连续段的长度则会 −ai-a_i，因此之后的每个 aia_i 等价于删去首尾各 aia_i 个数。

令 si=∑j=1iajs_i = \sum_{j = 1}^i a_j，找到最小的 ii 使得 x≤2six \le 2s_i。

对于 x≤2a1x \le 2a_1 的情况特殊处理。设做完前 2a12a_1 个操作后得到的序列为 p2p_2。

  • 若 x=six = s_i，则答案为 p2p_2 中第 l+si−a1l + s_i - a_1 个元素。
  • 若 x≤2si−1+aix \le 2s_{i - 1} + a_i，则答案为 p2p_2 中 [l+si−1−a1,l+x−si−1−a1][l + s_{i - 1} - a_1, l + x - s_{i - 1} - a_1] 中的最小值。
  • 若 x>2si−1+aix > 2s_{i - 1} + a_i，考虑做完 2si2s_i 次操作后时光倒流，这样又变成了取 min⁡\min 操作，答案为 p2p_2 中 [l+x−si−a1,l+si−a1][l + x - s_i - a_1, l + s_i - a_1] 中的最小值。

容易发现以上分析对一般序列也成立。

再考虑任意 aa 怎么做，按 aa 的前缀最大值分块，每一块都按以上方法处理。因为 ∑ai=n−12\sum a_i = \frac{n - 1}{2}，因此只会分成 O(n)O(\sqrt{n}) 段。

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
int tmp[150005];

void updatemin(int len) {
	deque<int> q;
	for (int i = n; i >= 1; i--) {
		while (!q.empty() && p[q.back()] > p[i]) q.pop_back();
		q.push_back(i);
		if (q.front() > i + len) q.pop_front();
		tmp[i] = p[q.front()];
	}
	n -= len;
	for (int i = 1; i <= n; i++) p[i] = tmp[i];
	return ;
}
void updatemax(int len) {
	deque<int> q;
	for (int i = n; i >= 1; i--) {
		while (!q.empty() && p[q.back()] < p[i]) q.pop_back();
		q.push_back(i);
		if (q.front() > i + len) q.pop_front();
		tmp[i] = p[q.front()];
	}
	n -= len;
	for (int i = 1; i <= n; i++) p[i] = tmp[i];
	return ;
}

namespace Subtask3 {
	int s[150005];
	struct query {int x, l, r, ans;} qry[150005];
	vector<int> vec[150005];
	struct SegmentTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

		int w[600005], l[600005], r[600005];

		void build(int ll, int rr, int now = 1) {
			l[now] = ll, r[now] = rr;
			if (ll == rr) {w[now] = p[ll]; return ;}
			int mid = (ll + rr) / 2;
			build(ll, mid, ls(now)), build(mid + 1, rr, rs(now));
			w[now] = min(w[ls(now)], w[rs(now)]);
			return ;
		}
		int query(int ll, int rr, int now = 1) {
			if (ll <= l[now] && r[now] <= rr) return w[now];
			int mid = (l[now] + r[now]) / 2, res = 0x3f3f3f3f;
			if (ll <= mid) res = min(res, query(ll, rr, ls(now)));
			if (mid < rr) res = min(res, query(ll, rr, rs(now)));
			return res;
		}

#undef ls
#undef rs
	} tr;
	struct SegmentTree2 {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

		int w[600005], l[600005], r[600005];

		void build(int ll, int rr, int now = 1) {
			l[now] = ll, r[now] = rr;
			if (ll == rr) {w[now] = p[ll]; return ;}
			int mid = (ll + rr) / 2;
			build(ll, mid, ls(now)), build(mid + 1, rr, rs(now));
			w[now] = max(w[ls(now)], w[rs(now)]);
			return ;
		}
		int query(int ll, int rr, int now = 1) {
			if (ll <= l[now] && r[now] <= rr) return w[now];
			int mid = (l[now] + r[now]) / 2, res = 0;
			if (ll <= mid) res = max(res, query(ll, rr, ls(now)));
			if (mid < rr) res = max(res, query(ll, rr, rs(now)));
			return res;
		}

#undef ls
#undef rs
	} tr2;

	void main() {
		for (int i = 1; i <= m; i++) s[i] = s[i - 1] + 2 * a[i];
		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d", &qry[i].x, &qry[i].l, &qry[i].r);
			int pos = lower_bound(s + 1, s + m + 1, qry[i].x) - s;
			vec[pos].push_back(i);
		}
		for (int i = 1, mx = 0, lstsum = 0; i <= n; i++) {
			if (mx < a[i]) {
				n -= 2 * (s[i - 1] - mx);
				for (int j = 1; j <= n; j++) p[j] = p[j + s[i - 1] - mx];
				s[i] = a[i], mx = a[i], lstsum += s[i - 1];
				tr.build(1, n);
				for (int j : vec[i]) {
					qry[j].x -= lstsum * 2;
					if (qry[j].x <= a[i]) qry[j].ans = tr.query(qry[j].l, qry[j].l + qry[j].x);
				}
				updatemin(a[i]);
				tr2.build(1, n);
				for (int j : vec[i])
					if (qry[j].x > a[i]) qry[j].ans = tr2.query(qry[j].l, qry[j].l + qry[j].x - a[i]);
				updatemax(a[i]);
				tr.build(1, n);
				continue;
			}
			s[i] = s[i - 1] + a[i];
			for (int j : vec[i]) {
				qry[j].x -= lstsum * 2;
				if (qry[j].x == 2 * s[i]) qry[j].ans = p[qry[j].l + s[i] - mx];
				else if (qry[j].x <= 2 * s[i - 1] + a[i])
					qry[j].ans = tr.query(qry[j].l + s[i - 1] - mx, qry[j].l + qry[j].x - s[i - 1] - mx);
				else qry[j].ans = tr.query(qry[j].l + qry[j].x - s[i] - mx, qry[j].l + s[i] - mx);
			}
		}
		for (int i = 1; i <= q; i++) printf("%d\n", qry[i].ans);
		return ;
	}
}

Subtask 4

只需求 fk=∑i=knmin⁡j=i−k+1iajf_k = \sum_{i = k}^n\min_{j = i - k + 1}^i a_j。

从前往后扫描线，维护以当前点为右端点的区间产生的贡献。设当前右端点为 rr，不妨认为 pr+1p_{r + 1} 到 pnp_n 均为 +∞+\infty，这样每次加一个点 rr 就会使 f1,f2,…,fn−r+1f_1, f_2, \ldots, f_{n - r + 1} 增加 ara_r。用单调栈维护后缀最小值，每次维护单调栈会使左端点在一个区间内的区间的答案加上一个值。具体地，设在区间 [l′,r′][l', r'] 中的左端点 ll 满足 min⁡i=lr−1ai=ar′\min_{i = l}^{r - 1} a_i = a_{r'} 且 ar′>ara_{r'} > a_r，则所有左端点在 [l′,r′][l', r'] 内，右端点在 [r,n][r, n] 内的区间的答案都要加上 ai−ar′a_i - a_{r'}。每个左端点对 ff 的贡献是一段区间，相邻两个左端点对应的区间是连续的（即两个区间的左端点的差等于右端点的差等于 11），用二阶差分维护即可。

Subtask 5

考虑把 Subtask 4 的做法升维，只需求 ft,k=∑i=ktmin⁡j=i−k+1iajf_{t, k} = \sum_{i = k}^t \min_{j = i - k + 1}^i a_j。

依然考虑扫描线，此时区间 [l,r][l, r] 会对所有的 t∈[r,n]t \in [r, n] 的 ft,r−l+1,ft,r−l+2,…,ft,t−l+1f_{t, r - l + 1}, f_{t, r - l + 2}, \ldots, f_{t, t - l + 1} 产生贡献，这是一个直角梯形。

因此每次产生的贡献就是若干个连续的直角梯形，这里连续是指上一个梯形向右平移一格得到下一个梯形。

对 ff 的每一行进行差分，这样一个梯形就变成了一条直线和一条斜率为 11 的斜线，多个梯形的贡献就是一个矩形和一个平行四边形。

把两个分开来算，矩形直接扫描线树状数组维护，然后变换坐标系，将 (x,y)(x, y) 变成 (x,y−x)(x, y - x)，这样平行四边形也变成了矩形。

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
namespace Subtask5 {
	struct BIT {
		long long w[150005];

		void update(int pos, long long val) {
			for (; pos < 150005; pos += pos & -pos) w[pos] += val;
			return ;
		}
		long long query(int pos) {
			long long res = 0;
			for (; pos >= 1; pos -= pos & -pos) res += w[pos];
			return res;
		}
	} bit1, bit2;
	struct query {int x, l, r;} qq[150005];
	long long ans[150005];
	vector<pair<int, int>> qry[150005];
	vector<tuple<int, int, int>> vec[150005];
	
	void update(int l, int r, long long val) {
		bit1.update(l, val), bit1.update(r + 1, -val);
		bit2.update(l, val * l), bit2.update(r + 1, -val * (r + 1));
		return ;
	}
	long long query(int r) {return bit1.query(r) * (r + 1) - bit2.query(r);}
	void solve(int op) {
		memset(bit1.w, 0, sizeof(bit1.w));
		memset(bit2.w, 0, sizeof(bit2.w));
		for (int i = 1; i <= n; i++) {
			for (auto j : vec[i]) update(get<0>(j), get<1>(j), get<2>(j));
			for (auto j : qry[i])
				if (j.second > 0) ans[j.second] += query(j.first + op * (n - i));
				else ans[-j.second] -= query(j.first + op * (n - i));
		}
		return ;
	}

	void main() {
		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d", &qq[i].x, &qq[i].l, &qq[i].r);
			if (qq[i].x > a[1]) continue;
			qq[i].l += qq[i].x, qq[i].r += qq[i].x;
			qry[qq[i].r].emplace_back(qq[i].x + 1, i);
			qry[qq[i].l - 1].emplace_back(qq[i].x + 1, -i);
		}
		vector<int> stk;
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && p[stk.back()] >= p[i]) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				vec[i].emplace_back(i - r + 1, i - l + 1, p[i] - p[r]);
			}
			// t in [i, n], k in [1, t - i + 1]
			vec[i].emplace_back(1, 1, p[i]);
			stk.push_back(i);
		}
		solve(0);
		for (int i = 1; i <= n; i++) vector<tuple<int, int, int>>().swap(vec[i]);
		vector<int>().swap(stk);
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && p[stk.back()] >= p[i]) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				vec[i].emplace_back(n - r + 2, n - l + 2, p[r] - p[i]);
			}
			// t in [i, n], k in [1, t - i + 1]
			vec[i].emplace_back(n - i + 2, n - i + 2, -p[i]);
			stk.push_back(i);
		}
		solve(1);
		updatemin(a[1]);
		for (int i = 1; i <= n; i++) vector<pair<int, int>>().swap(qry[i]);
		for (int i = 1; i <= q; i++) {
			if (qq[i].x <= a[1]) continue;
			qq[i].x -= a[1];
			qq[i].l += qq[i].x, qq[i].r += qq[i].x;
			qry[qq[i].r].emplace_back(qq[i].x + 1, i);
			qry[qq[i].l - 1].emplace_back(qq[i].x + 1, -i);
		}
		for (int i = 1; i <= n; i++) vector<tuple<int, int, int>>().swap(vec[i]);
		vector<int>().swap(stk);
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && p[stk.back()] <= p[i]) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				vec[i].emplace_back(i - r + 1, i - l + 1, p[i] - p[r]);
			}
			// t in [i, n], k in [1, t - i + 1]
			vec[i].emplace_back(1, 1, p[i]);
			stk.push_back(i);
		}
		solve(0);
		for (int i = 1; i <= n; i++) vector<tuple<int, int, int>>().swap(vec[i]);
		vector<int>().swap(stk);
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && p[stk.back()] <= p[i]) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				vec[i].emplace_back(n - r + 2, n - l + 2, p[r] - p[i]);
			}
			// t in [i, n], k in [1, t - i + 1]
			vec[i].emplace_back(n - i + 2, n - i + 2, -p[i]);
			stk.push_back(i);
		}
		solve(1);
		for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
		return ;
	}
}

Subtask 6

按 Subtask3 的方法分块后，每个点的值就变成了一个区间最值，区间的和就是若干个连续的区间的最值的和，发现这个形式和 Subtask 5 的形式一模一样，直接用 Subtask 5 的方法做即可，时间复杂度为 O(nnlog⁡n+qlog⁡n)O(n\sqrt{n}\log n + q\log n)。

Subtask 7

平衡一下复杂度，用 O(1)O(1) 修改 O(n)O(\sqrt{n}) 查询的分块代替树状数组即可做到 O((n+q)n)O((n + q)\sqrt{n})​。

Subtask 6 和 Subtask 7 均需注意常数优化。

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <tuple>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, q, p[150005], a[150005];
int tmp[150005];

void updatemin(int len) {
	deque<int> q;
	for (int i = n; i >= 1; i--) {
		while (!q.empty() && p[q.back()] > p[i]) q.pop_back();
		q.push_back(i);
		if (q.front() > i + len) q.pop_front();
		tmp[i] = p[q.front()];
	}
	n -= len;
	for (int i = 1; i <= n; i++) p[i] = tmp[i];
	return ;
}
void updatemax(int len) {
	deque<int> q;
	for (int i = n; i >= 1; i--) {
		while (!q.empty() && p[q.back()] < p[i]) q.pop_back();
		q.push_back(i);
		if (q.front() > i + len) q.pop_front();
		tmp[i] = p[q.front()];
	}
	n -= len;
	for (int i = 1; i <= n; i++) p[i] = tmp[i];
	return ;
}

namespace Subtask7 {
	const int B = 387;

	struct decompose {
		long long w[150005], sum[B + 5];

		void clear() {memset(w, 0, sizeof(w)); memset(sum, 0, sizeof(sum)); return ;}
		void update(int pos, long long val) {w[pos] += val, sum[(pos - 1) / B + 1] += val; return ;}
		long long query(int pos) {
			long long res = 0;
			int limit = (pos - 1) / B;
			for (int i = 1; i <= limit; i++) res += sum[i];
			for (int i = limit * B + 1; i <= pos; i++) res += w[i];
			return res;
		}
	} dc1, dc2;
	int s[150005];
	struct query {int x, l, r; long long ans;} qry[150005];
	vector<int> id[150005];
	vector<pair<int, int>> qq[150005];

	void update(int l, int r, long long val) {
		dc1.update(l, val), dc1.update(r + 1, -val);
		dc2.update(l, val * l), dc2.update(r + 1, -val * (r + 1));
		return ;
	}
	long long query(int r) {return dc1.query(r) * (r + 1) - dc2.query(r);}
	void solve(int op) {
		dc1.clear(), dc2.clear();
		vector<int> stk;
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && (!op ? p[stk.back()] >= p[i] : p[stk.back()] <= p[i])) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				update(i - r + 1, i - l + 1, p[i] - p[r]);
			}
			// t in [i, n], k in [1, t - i + 1]
			update(1, 1, p[i]);
			stk.push_back(i);
			for (auto j : qq[i])
				if (j.second > 0) qry[j.second].ans += query(j.first);
				else qry[-j.second].ans -= query(j.first);
		}
		dc1.clear(), dc2.clear();
		stk.clear();
		for (int i = 1; i <= n; i++) {
			while (!stk.empty() && (!op ? p[stk.back()] >= p[i] : p[stk.back()] <= p[i])) {
				int r = stk.back();
				stk.pop_back();
				int l = (!stk.empty() ? stk.back() : 0) + 1;
				// t in [i, n], k in [i - ll + 1, t - ll + 1] (tips: ll in [l, r])
				update(n - r + 2, n - l + 2, p[r] - p[i]);
			}
			// t in [i, n], k in [1, t - i + 1]
			update(n - i + 2, n - i + 2, -p[i]);
			stk.push_back(i);
			for (auto j : qq[i])
				if (j.second > 0) qry[j.second].ans += query(j.first + n - i);
				else qry[-j.second].ans -= query(j.first + n - i);
		}
		return ;
	}

	void main() {
		for (int i = 1; i <= m; i++) s[i] = s[i - 1] + 2 * a[i];
		for (int i = 1; i <= q; i++) {
			scanf("%d%d%d", &qry[i].x, &qry[i].l, &qry[i].r);
			int pos = lower_bound(s + 1, s + m + 1, qry[i].x) - s;
			id[pos].push_back(i);
		}
		for (int l = 1, r, lstsum = 0, lst = 0; l <= m; lst = l, l = r + 1) {
			r = l;
			while (r < m && a[r + 1] <= a[l]) r++;
			n -= 2 * (s[l - 1] - a[lst]);
			for (int i = 1; i <= n; i++) p[i] = p[i + s[l - 1] - a[lst]];
			lstsum += s[l - 1];
			for (auto i : id[l]) {
				qry[i].x -= lstsum * 2;
				if (qry[i].x <= a[l]) {
					int x = qry[i].x, ll = qry[i].l + x, rr = qry[i].r + x;
					qq[rr].emplace_back(x + 1, i);
					qq[ll - 1].emplace_back(x + 1, -i);
				}
			}
			solve(0);
			for (int i = 1; i <= n; i++) qq[i].clear();
			updatemin(a[l]);
			for (int i : id[l])
				if (qry[i].x > a[l]) {
					int x = qry[i].x - a[l], ll = qry[i].l + x, rr = qry[i].r + x;
					qq[rr].emplace_back(x + 1, i);
					qq[ll - 1].emplace_back(x + 1, -i);
				}
			solve(1);
			for (int i = 1; i <= n; i++) qq[i].clear();
			updatemax(a[l]);
			s[l] = a[l];
			for (int i = l + 1; i <= r; i++) {
				s[i] = s[i - 1] + a[i];
				for (int j : id[i]) {
					qry[j].x -= lstsum * 2;
					int x, ll, rr;
					if (qry[j].x == 2 * s[i]) {
						x = 0;
						ll = qry[j].l + s[i] - a[l];
						rr = qry[j].r + s[i] - a[l];
					} else if (qry[j].x <= 2 * s[i - 1] + a[i]) {
						x = qry[j].x - 2 * s[i - 1];
						ll = qry[j].l + qry[j].x - s[i - 1] - a[l];
						rr = qry[j].r + qry[j].x - s[i - 1] - a[l];
					} else {
						x = 2 * s[i] - qry[j].x;
						ll = qry[j].l + s[i] - a[l];
						rr = qry[j].r + s[i] - a[l];
					}
					qq[rr].emplace_back(x + 1, j);
					qq[ll - 1].emplace_back(x + 1, -j);
				}
			}
			solve(0);
			for (int i = 1; i <= n; i++) qq[i].clear();
		}
		for (int i = 1; i <= q; i++) printf("%lld\n", qry[i].ans);
		return ;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
	for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
	Subtask7::main();
	return 0;
}
留言