[CF436D]Pudding Monsters

题目大意：有一个长度为$2 imes 10^5$的板，有$n(nleqslant 10^5)$个格子$a_1,dots,a_n$有布丁怪兽，一开始连续的怪兽算一个怪兽，有$m(mleqslant 2000)$个特殊点$b_1,dots,b_n$，你可以向左或向右移动怪兽，它会在碰到第一怪兽时停下，并成为一个怪兽。最左边和最右边的怪兽向两边移动会掉出板。问最多可以让布丁怪兽压到几个特殊点。

题解：先把连续的布丁怪兽看做长度个不同的怪兽，令$f_i$表示前$i$个怪兽最多可以覆盖多少个点，$g_i$表示前$i$个怪兽且第$i$个怪兽不动可以覆盖最多的点，$sum_{l,r}$表示$[l,r]$中特殊点个数

设当前转移坐标为$a_i$

1. 这个位置向左移，那么枚举$b_j$满足$b_jleqslant a_i$，要覆盖区间$[b_j,a_i]$，就需要另外的$len=a_i-b_j$个怪兽，则

$$
g_i=max{g_i,f_{i-len-1}+sum_{b_j,a_i}}
$$

2. 这个位置向右移，那么枚举$b_j$满足$b_jgeqslant a_i$，要覆盖区间$[a_i,b_j]$，需要另外$len=b_j-a_i$个怪兽，则

$$
f_{i+len}=max{f_{i+len},g_i+sum_{a_i+1,b_j}}
$$

3. 这个位置不动，则
$$
f_i=max{f_i,g_i,f_{i-1}+sum_{a_i,a_i}}\
g_i=max{g_i,f_{i-1}+sum_{a_i,a_i}}
$$

因为最开始怪兽有连续的，所以记录每个布丁怪兽的左端点和右端点，移动的时候将一整个怪兽移动即可

卡点：$f_i$没有用$g_i$更新，$g_i$使用了$g_{i-1}$来转移导致调了很久

C++ Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
const int maxn = 1e5 + 10;
#define chkmax(a, b) (a = std::max(a, b))

int n, m;
int a[maxn], b[maxn], L[maxn], R[maxn];
int s[200010], f[maxn], g[maxn];
inline int sum(int a, int b) { return s[b] - s[a - 1]; }
inline int sum(int a) { return s[a] - s[a - 1]; }

int main() {
	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	for (int i = 1; i <= m; ++i) std::cin >> b[i], ++s[b[i]];
	for (int i = 1; i <= 200000; ++i) s[i] += s[i - 1];
	std::sort(a + 1, a + n + 1), std::sort(b + 1, b + m + 1);
	a[0] = -20040826, a[n + 1] = 20040826;
	for (int i = 1; i <= n; ++i)
		if (a[i] != a[i - 1] + 1) L[i] = i;
		else L[i] = L[i - 1];
	for (int i = n; i; --i)
		if (a[i] != a[i + 1] - 1) R[i] = i;
		else R[i] = R[i + 1];

	for (int i = 1; i <= n; ++i) {
		chkmax(f[i], f[i - 1] + sum(a[i]));
		chkmax(g[i], f[i - 1] + sum(a[i]));
		for (int j = 1, len; j <= m && b[j] <= a[i]; ++j)
			if ((len = a[i] - b[j]) < i)
				chkmax(g[i], f[L[i - len] - 1] + sum(b[j], a[i]));
		chkmax(f[i], g[i]);
		for (int j = m, len; j && b[j] >= a[i]; --j)
			if ((len = b[j] - a[i]) <= n - i)
				chkmax(f[R[i + len]], g[i] + sum(a[i] + 1, b[j]));
	}
	std::cout << f[n] << '
';
	return 0;
}