题解：P7482 不条理狂诗曲

本题解借鉴 blossom_j 大佬思路，但这位大佬的题解似乎没放正确代码。

题意

对于每一个 \(a\) 的子区间 \(a_{l\dots r}\)，求选择若干个不连续的数的和的最大值，对答案取模 \(10^{9}+7\)。

思路

主要算法：分治。

计算跨过中点 \(mid\) 的区间的 \(f\) 之和。

首先我们可以写一个 DP。\(f_{i,0/1,0/1}\) 表示 DP 已到达 \(i\) 的位置。第一个 \(0/1\) 表示 \(mid\) 或 \(mid+1\) 是否被选择。第二个 \(0/1\) 表示是否选择了第 \(i\) 个元素。

枚举 \(l\) 对所有的 \(r\) 求和：设 \(g_{i,j}=\max\{f_{i,j,0},f_{i,j,1}\}\)。区间 $\left [ l,r \right ] $ 的答案就是 \(\max\{g_{l,0}+\max\{g_{r,0},g_{r,1}\},g_{l,1}+g_{r,0}\}\)。

若 \(g_{l,0}-g_{l,1}\le g_{r,0}-\max\{g_{r,0},g_{r,1}\}\)，则必需选择后者。

将 \(g_{r,0}-\max\{g_{r,0},g_{l,1}\}\) 排序，二分寻找分界点。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1000000007, Maxn = 2 * 1e5 + 10;
int n, a[Maxn], ans = 0, f[Maxn][2][2], g[Maxn][2],sa[Maxn], sb[Maxn];
struct Node {
	int date, ID;
} d[Maxn];

bool  cmp(Node x, Node y) {
	return x.date < y.date;
}

int ask(int x, int l, int r) {
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (d[mid].date <= x)l = mid;
		else r = mid - 1;
	}
	return l;
}

void solve(int l, int r) {
	if (l == r) {
		ans = (ans + a[l]) % mod;
		return;
	}

	int mid = (l + r) >> 1;
	f[mid + 1][0][0] = f[mid + 1][0][1] = f[mid + 1][1][0] = 0, f[mid + 1][1][1] = a[mid + 1];

	g[mid + 1][0] = f[mid + 1][0][0];
	g[mid + 1][1] = f[mid + 1][1][1];

	d[mid + 1].ID = mid + 1;
	d[mid + 1].date = g[mid + 1][0] - max(g[mid + 1][0], g[mid + 1][1]);


	for (int i = mid + 2; i <= r; i++) {
		f[i][0][0] = max(f[i - 1][0][0], f[i - 1][0][1]);
		f[i][1][0] = max(f[i - 1][1][0], f[i - 1][1][1]);
		f[i][0][1] = f[i - 1][0][0] + a[i];
		f[i][1][1] = f[i - 1][1][0] + a[i];

		g[i][0] = max(f[i][0][0], f[i][0][1]);
		g[i][1] = max(f[i][1][0], f[i][1][1]);

		d[i].ID = i;
		d[i].date = g[i][0] - max(g[i][0], g[i][1]);
	}


	sort(d + mid + 1, d + r + 1, cmp);

	sa[mid] = sb[mid] = sa[r + 1] = sb[r + 1] = 0;
	for (int i = mid + 1; i <= r + 1; i++) {
		sa[i] = sa[i - 1] + g[d[i].ID][0];
		sb[i] = sb[i - 1] + max(g[d[i].ID][0], g[d[i].ID][1]);
	}

	f[mid][0][0] = f[mid][0][1] = f[mid][1][0] = 0, f[mid][1][1] = a[mid];

	g[mid][0] = f[mid][0][0];
	g[mid][1] = f[mid][1][1];

	int k = ask(g[mid][0] - g[mid][1], mid, r);
	ans = (ans + g[mid][0] * (k - mid) % mod + sb[k] + sa[r] - sa[k] + g[mid][1] * (r - k) % mod + mod) % mod;

	for (int i = mid - 1; i >= l; i--) {
		f[i][0][0] = max(f[i + 1][0][0], f[i + 1][0][1]);
		f[i][1][0] = max(f[i + 1][1][0], f[i + 1][1][1]);
		f[i][0][1] = f[i + 1][0][0] + a[i];
		f[i][1][1] = f[i + 1][1][0] + a[i];

		g[i][0] = max(f[i][0][0], f[i][0][1]);
		g[i][1] = max(f[i][1][0], f[i][1][1]);

		int k = ask(g[i][0] - g[i][1], mid, r);
		ans = (ans + g[i][0] * (k - mid) % mod + sb[k] + sa[r] - sa[k] + g[i][1] * (r - k) % mod + mod) % mod;
	}

	solve(l, mid), solve(mid + 1, r);
}
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	solve(1, n);
	cout << ans << '\n';
	return 0;
}