BZOJ 4385 Wilcze doły

发表于 | 更新于

Link

看出来应该是根据单调性来O(n)O(n)做 双指针？不好弄 三指针？不好弄 五指针？贰叁叁

Solution

预处理出从每个点开始长度为dd的区间和g[]g[] 枚举rr，找出当前合法的最靠前的ll。合法的话，需要保证Sum(l,r)−max{g[l∼r−d+1]}<pSum(l,r)-max\{g[l\sim r-d+1]\}< p 这个最大值用单调队列维护即可。

Tips

基于单调性的O(n)O(n)做法有多种，不应该只纠结于

Code

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
#include "lucida"
using std::partial_sum;
using std::max;
const int MAXN=2000000+11;
int main() {
//	freopen("input","r",stdin);
	static int64 w[MAXN],pref[MAXN],dsum[MAXN];
	static int Q[MAXN],he,ta;
	int n,d;int64 p;is>>n>>p>>d;
	for(int i=1;i<=n;++i)
		is>>w[i];
	partial_sum(w+1,w+1+n,pref+1);
	for(int i=1;i<=n;++i) 
		dsum[i]=pref[i]-pref[i-d>=0?i-d:0];
	int Ans=0;
	for(int l=1,r=1;r<=n;++r) {
		while(he<=ta && dsum[Q[ta]]<dsum[r]) 
			ta--;
		Q[++ta]=r;
		while(l<=r && he<=ta && pref[r]-pref[l-1]-dsum[Q[he]]>p) {
			l++;
			while(he<=ta && Q[he]-d+1<l)
				he++;
		}
		if(pref[r]-pref[l-1]-dsum[Q[he]]<=p)
			chkmx(Ans,r-l+1);
	}
	os<<Ans<<'\n';
	return 0;
}