自动搬运

查看原文

来自洛谷，原作者为

	Starlight237 [Drawer/auth]EgcqEzGZV+k435xMKiYIpABsjWY0ln/huv6DW7QW9Qw=

搬运于2025-08-24 22:25:27，当前版本为作者最后更新于2021-11-04 23:47:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小清新双指针+树状数组，不需要离散化/主席树/平衡树之类的东西。

(2021集训队作业 P6958 【[NEERC2017]The Great Wall】)给定三个序列 $\{a_{0,n}\},\{a_{1,n}\},\{a_{2,n}\}(a_{i,j}<a_{i+1,j})$，你需要选择两个不同的长度为 $r$ 的区间 $I,J$，使得 $w(I,J)$ 是所有情况中第 k 小的。定义 $w(I,J)=\sum a_{[i\in I]+[i\in J],i}$。注意，$(I,J)$ 和 $(J,I)$ 视为相同的方案。

考虑二分答案 $x$，转化为统计答案不超过 $x$ 的方案个数是否至少有 k 个。首先可以将 $a_{1}$ 和 $a_2$ 中每个元素都减去 $a_0$ 对应位置的元素，最后答案加上 $a_0$ 中所有元素之和，转换成对于两个数组的问题 $b_{1,i}=a_{1,i}-a_{0,i},b_{2,i}=a_{2,i}-a_{0,i}$。

Case 1. $I\cap J=\varnothing$

设两个区间分别为 $I=[s,s+r-1]$ 和 $J=[t,t+r-1]$，则 $w(I,J)=\sum_{i\in I}b_{1,i}+\sum_{j\in J}b_{1,i}$，考虑前缀和优化，令 $pre_i=\sum_{j=1}^ib_{1,j}$，则 $w(I,J)=pre_{s+r-1}-pre_{s-1}+pre_{t+r-1}-pre_{t-1}$。设 $f_i=pre_{i+r-1}-pre_{i-1}$，则 $w(I,J)=f_s+f_t$。于是需要求出有多少对 $s,t$，满足 $1\le s\le n-2r+1,s+r\le t\le n-r+1,f_s+f_t< x$(我们不妨设 $J$ 在 $I$ 右边)，显然是一个二维数点问题。

Case 2. $I\cap J\not=\varnothing$

则 $w(I,J)=\sum_{i=s}^{t-1}b_{1,i}+\sum_{i=t}^{s+r-1}b_{2,i}+\sum_{i=s+r}^{t+r-1}b_{1,i}$，再令 $pre'_i=\sum_{j=1}^ib_{2,j},g_i=pre'_{i+r-1}-pre_{i-1}-pre_{i+r-1},h_i=pre_{i-1}-pre'_{i-1}+pre_{i+r-1}$，则 $w(I,J)=g_s+h_t$。于是也是一个二维数点：$1\le s< n-r+1,s< t\le\min(s+r-1,n-r+1),g_i+h_i< x$

双指针+BIT 即可。

#define ll long long
#define pli pair<ll, int>
const int N = 30010;
int n, m, r, k, tr[N];
ll a[N], b[N], c[N];
pli f[N], g[N], h[N];
#define lowbit(x) ((x) & -(x))
inline void add(int x, int v) {
	for (; x <= m; x += lowbit(x)) tr[x] += v;
}
inline int qry(int x) {
	int sm = 0;
	for (; x > 0; x -= lowbit(x)) sm += tr[x];
	return sm;
}
inline int calc(ll x) {
	memset(tr, 0, sizeof tr);
	int cnt = 0;
	for (int t = m, s = 1; t; --t) {
		for (; s <= m && f[s].first + f[t].first <= x; ++s) add(f[s].second, 1);
		cnt += qry(f[t].second - r);
	}
	memset(tr, 0, sizeof tr);
	for (int t = m, s = 1; t; --t) {
		for (; s <= m && g[s].first + h[t].first <= x; ++s) add(g[s].second, 1);
		cnt += qry(h[t].second - 1) - qry(h[t].second - r);
	}
	return cnt;
}
int main() {
	n = rd(), r = rd(), k = rd(), m = n - r + 1;
	ll sm = 0;
	for (int i = 1; i <= n; ++i) a[i] = rd(), sm += a[i];
	for (int i = 1; i <= n; ++i) b[i] = b[i - 1] + rd() - a[i];
	for (int i = 1; i <= n; ++i) c[i] = c[i - 1] + rd() - a[i];
	for (int i = 1; i <= m; ++i)
		f[i] = make_pair(b[i + r - 1] - b[i - 1], i),
		g[i] = make_pair(c[i + r - 1] - b[i - 1] - b[i + r - 1], i),
		h[i] = make_pair(b[i - 1] - c[i - 1] + b[i + r - 1], i);
	sort(f + 1, f + m + 1), sort(g + 1, g + m + 1), sort(h + 1, h + m + 1);
	ll l = 0, r = c[n], mid, ans = 0;
	while (l <= r)
		mid = l + r >> 1, calc(mid) >= k ? ans = mid, r = mid - 1 : l = mid + 1;
	printf("%lld", sm + ans);
	return 0;
}