[BZOJ]4385: [POI2015]Wilcze doły

题解:n的范围告诉这题做法是线性的 .....如果没有d这个操作那好像就直接双指针扫过去就行了现在有了d的限制我们只需要把一段区间里面连续长度为d且和最大那一段赋值为0即可这样我们可以通过单调队列实现综合两者在双指针扫描同时维护合法区间的最大连续d的和然后check即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e6+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n,d;ll p;
ll c[MAXN];
int st[MAXN],l,r;


int main(){
    n=read();p=read();d=read();
    inc(i,1,n)c[i]=read(),c[i]+=c[i-1];
    l=r=0;l=1;
    st[++r]=d;int j=d+1;int i=1;
    int ans=0;
    while(i<=n){
	//cout<<i<<"::"<<" "<<j-1<<" "<<st[l]<<endl;
	while(l<=r&&st[l]<i+d-1)l++;
	if(c[j-1]-c[i-1]-c[st[l]]+c[st[l]-d]>p){i++;continue;}
	ans=max(ans,j-i);
	while(j<=n){
	    while(l<=r&&c[st[r]]-c[st[r]-d]<=c[j]-c[j-d])r--;
	    st[++r]=j;
	    if(c[j]-c[i-1]-c[st[l]]+c[st[l]-d]>p){ans=max(ans,j-i);j++;break;}
	    j++;
	    ans=max(ans,j-i);
	}
	i++;
    }
    printf("%d
",ans);
}

4385: [POI2015]Wilcze doły

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1039 Solved: 437
[Submit][Status][Discuss]

Description

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。
请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

Input

第一行包含三个整数n,p,d(1<=d<=n<=2000000，0<=p<=10^16)。
第二行包含n个正整数，依次表示序列中每个数w[i](1<=w[i]<=10^9)。

Output

包含一行一个正整数，即修改后能找到的最长的符合条件的区间的长度。

Sample Input