[POI2015]Wilcze doły

题目大意：

给定一个长度为\(n(n\le2\times10^6)\)的数列\(A(1\le A_i\le10^9)\)，可以从中选取不超过\(d\)个连续数字变成\(0\)，求一个最长的子串使得这段数的和不超过\(p\)。

思路1：

显然，将\(d\)个修改的机会用完一定最优，答案至少为\(d\)。

二分答案\(k\)，\(O(n)\)枚举端点，若区间和-区间最大的长度为\(d\)的子段和\(\le p\)，则答案至少为\(k\)。

而“区间最大的长度为\(d\)的子段和”可以用稀疏表维护，时空复杂度均为\(\mathcal O(n\log n)\)。

然而这题空间限制128MB，还要开int64，会MLE，要是空间开到512MB也能过了。

源代码1：

#include<cstdio>

#include<cctype>

#include<algorithm>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=2e6+1,logN=21;

int n,a[N],d;

int64 p,sum[N],max[N][logN];

inline int lg2(const float &x) {

	return ((unsigned&)x>>23&255)-127;

}

inline bool check(const int &k) {

	for(register int i=k;i<=n;i++) {

		const int l=lg2(k-d+1);

		if(sum[i]-sum[i-k]-std::max(max[i-k+d][l],max[i-(1<<l)+1][l])<=p) return true;

	}

	return false;

}

int main() {

	n=getint(),p=getint(),d=getint();

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

		sum[i]=sum[i-1]+a[i];

		if(i>=d) max[i][0]=sum[i]-sum[i-d];

	}

	for(register int j=1;j<=lg2(n-d+1);j++) {

		for(register int i=d;i<=n;i++) {

			max[i][j]=std::max(max[i][j-1],max[i+(1<<(j-1))][j-1]);

		}

	}

	int l=d+1,r=n;

	while(l<=r) {

		const int mid=(l+r)>>1;

		if(check(mid)) {

			l=mid+1;

		} else {

			r=mid-1;

		}

	}

	printf("%d\n",l-1);

	return 0;

}

思路2：

不难发现当右端点单调递增时，能选取的最大的左端点具有单调性。

而“区间最大的长度为\(d\)的子段和”可以用单调队列维护。

时空复杂度\(\mathcal O(n)\)。

源代码2：

#include<queue>

#include<cstdio>

#include<cctype>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=2e6+1;

std::deque<int> q;

int a[N];

int64 sum[N],tmp[N];

int main() {

	const int n=getint();

	const int64 p=getint();

	const int d=getint();

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

		sum[i]=sum[i-1]+a[i];

		if(i>=d) tmp[i]=sum[i]-sum[i-d];

	}

	int ans=d;

	q.push_back(d);

	for(register int i=d+1,last=0;i<=n;i++) {

		while(!q.empty()&&q.front()-d<last) q.pop_front();

		while(!q.empty()&&tmp[q.back()]<=tmp[i]) q.pop_back();

		q.push_back(i);

		while(!q.empty()&&sum[i]-sum[last]-tmp[q.front()]>p) {

			last++;

			if(!q.empty()&&q.front()-d<last) q.pop_front();

		}

		ans=std::max(ans,i-last);

	}

	printf("%d\n",ans);

	return 0;

}