[AGC009C] Division into Two

先假定 \(A\le B\)，然后先判断无解，
如果 \(a_{i+2}-a_i<B\)，无论怎么分配都是不合法的，直接判掉。
然后考虑 dp，\(f_i\) 表示选了前 \(i\) 个数，其中第 \(i\) 个数是归为 \(A\) 集合的方案数。
其中不难发现可转移的状态是一段区间，状态 \(f_j\) 可以转移仅当 \(a_i-a_j \ge A\) 且 \(a_{j+1}\) 到 \(a_{j-1}\) 都可以被归到 \(B\) 集合。
使用前缀和优化，时间复杂度 \(O(n)\)。

const int N = 1e5 + 5;
int n;
ll A, B, a[N];
int f[N], s[N];
void solve() {
	cin >> n >> A >> B;
	if(A < B) swap(A, B);
	FOR(i, 1, n) cin >> a[i];
	FOR(i, 1, n - 2) {
		if(a[i + 2] - a[i] < B) {
			cout << 0 << endl;
			return;
		}
	}
	f[0] = s[0] = 1;
	int l = 0, r = 0;
	FOR(i, 1, n) {
		while(l < i && a[i] - a[l + 1] >= A) l++;
		if(r <= l) f[i] = (s[l] - (r ? s[r - 1] : 0) + P) % P;
		s[i] = (s[i - 1] + f[i]) % P;
		if(i > 1 && a[i] - a[i - 1] < B) r = i - 1; 
	}
	int ans = 0;
	ROF(i, n, 0) {
		ans = (ans + f[i]) % P;
		if(i < n && a[i + 1] - a[i] < B) break;
	}
	cout << ans << endl;
}