题解 P5922 【[COCI 2011] Dvoniz】
Great_Influence
2020-01-19 14:31:56
一个位置向右 $2k$ 的序列是否合法是不具有单调性的， 不能使用单调栈记录。
我们考虑直接计算出以 $i$ 和 $i + 1$ 为中心的合法序列最长有多长。 假设长度为 $K_i$ ，我们可以直接将 $i-K_i+1$ 的答案更新成 $K_i$ 。
然后，容易发现， $ans_i \ge ans_{i-1} -1$ 。
再次从头向后扫一遍更新即可。
时间复杂度 $O(n)$ 。
代码:
```cpp
#include<bits/stdc++.h>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mp make_pair
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;
namespace IO
{
const uint32 Buffsize=1<<15,Output=1<<24;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
}
static char Out[Output],*nowps=Out;
inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
template<typename T>inline void read(T&x)
{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
x*=f;
}
template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static uint32 sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
if(nowps-Out>=1<<23)flush();
}
inline void getstr(char*q)
{
register char ch;
for(ch=getc();!isgraph(ch);ch=getc());
for(;isgraph(ch);ch=getc())*q++=ch;
*q='\0';
}
inline void getwd(char&x){for(x=getc();!isupper(x);x=getc());}
}
using namespace IO;
void file()
{
#ifndef ONLINE_JUDGE
FILE*DSD=freopen("a.in","r",stdin);
FILE*CSC=freopen("a.out","w",stdout);
#endif
}
inline void Chkmin(int&u,int v){u>v?u=v:0;}
inline void Chkmax(int&u,int v){u<v?u=v:0;}
inline void Chkmax(double&u,double v){u<v?u=v:0;}
inline void Chkmax(ll&u,ll v){u<v?u=v:0;}
inline void Chkmin(ll&u,ll v){u>v?u=v:0;}
const int MAXN = 1e5 + 7;
static int n, s, a[MAXN];
inline void init()
{
read(n), read(s);
Rep(i, 1, n) read(a[i]);
}
static int ans[MAXN], pr[MAXN];
inline void solve()
{
static int sm = 0, as = 0;
Rep(i, 1, n)
{
while(i + as <= n && sm <= s - a[i + as]) sm += a[i + as], ++as;
pr[i] = as;
if(as)sm -= a[i], --as;
}
Repe(i, n, 1)
{
while(i > as && sm <= s - a[i - as]) sm += a[i - as], ++as;
if(as) sm -= a[i], Chkmax(ans[i - min(as, pr[i + 1]) + 1], min(as, pr[i + 1])), --as;
}
Rep(i, 1, n) write(ans[i] << 1), Chkmax(ans[i + 1], ans[i] - 1);
flush();
}
int main()
{
file();
init();
solve();
return 0;
}
```