题目大意
给定长为$n$的由$0,-1,1$组成的序列。给定$L,R$，你要把整个序列分成若干段，使得，每一段的长度$in [L,R]$，设某一段的和为$x$，则当$x>0$时它对答案有$+1$的贡献，当$x<0$时它对答案有$-1$的贡献，当$x=0$时它对答案无贡献。
题解
用$S_i$表示第$i$位的前缀和。
很容易想到用单调队列来维护些什么，可是你会发现转移方程长这样
$F_i=max{ F_j+(S_i>S_j)-(S_i<S_j)}(jin[i-R,i-L])$，转移过程与$S_i$和$S_j$大小关系有关，所以需要将方法转化。
不难发现$F_i$的值一定$in [-n,+n]$，所以可以考虑对于每一种$S$维护单调队列，用线段树维护每一个$S_j$在$jin [i-R,i-L]$的单调队列对队首的最大值。每次转移时从$S_j<S_i$出找到最大的$F$值并$+1$进行转移，其余情况同理即可。
时间复杂度$O(nlog n)$
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define M 1001000
using namespace std;
int read(){
int nm=0,fh=1; int cw=getchar();
for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
int p[M<<3],F[M],n,m,fs[M<<1],fin[M<<1],last[M<<1],nt[M<<1],L,R,t[M];
void build(int x,int l,int r){
p[x]=-(M<<1); if(l==r) return; int mid=((l+r)>>1);
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
void upd(int x,int l,int r,int ps){
if(l==r){p[x]=(fs[ps]==-1?-(M<<1):F[fs[ps]]);return;}
int mid=((r+l)>>1);
if(ps<=mid) upd(x<<1,l,mid,ps); else upd(x<<1|1,mid+1,r,ps);
p[x]=max(p[x<<1],p[x<<1|1]);
}
void ins(int ps,int x){
if(F[x]<-n) return;
while(fin[ps]>=0&&F[fin[ps]]<F[x]) fin[ps]=last[fin[ps]];
if(fin[ps]==-1) fs[ps]=fin[ps]=x,last[x]=-1,upd(1,M-n,M+n,ps);
else nt[fin[ps]]=x,last[x]=fin[ps],fin[ps]=x; nt[fin[ps]]=-1;
}
void del(int ps,int x){
if(fs[ps]!=x) return; fs[ps]=nt[fs[ps]],last[fs[ps]]=-1;
if(fin[ps]==x) fin[ps]=fs[ps],nt[fin[ps]]=-1; upd(1,M-n,M+n,ps);
}
int qf(int x,int l,int r,int rs){
if(rs<l||p[x]<-n) return -(M<<1);
if(r==rs) return p[x]; int mid=((l+r)>>1);
if(rs<=mid) return qf(x<<1,l,mid,rs);
return max(qf(x<<1|1,mid+1,r,rs),p[x<<1]);
}
int qb(int x,int l,int r,int ls){
if(ls>r||p[x]<-n) return -(M<<1);
if(l==ls) return p[x]; int mid=((l+r)>>1);
if(ls>mid) return qb(x<<1|1,mid+1,r,ls);
return max(qb(x<<1,l,mid,ls),p[x<<1|1]);
}
int main(){
freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
n=read(),L=read(),R=read(),build(1,M-n,M+n);
memset(fs,-1,sizeof(fs)),memset(fin,-1,sizeof(fin));
for(int i=1;i<=n;i++){
int res; t[i]=read()+t[i-1],F[i]=-(M<<1);
if(i<L) continue; ins(t[i-L]+M,i-L);
if(i>R) del(t[i-R-1]+M,i-R-1);
res=qf(1,M-n,M+n,M+t[i]-1),F[i]=max(F[i],res+1);
res=qb(1,M-n,M+n,M+t[i]+1),F[i]=max(F[i],res-1);
res=(fs[t[i]+M]==-1?-(M<<1):F[fs[t[i]+M]]),F[i]=max(F[i],res);
}
if(F[n]<-n) puts("Impossible");
else printf("%d
",F[n]); return 0;
}
当然这条题$nleq 10^6$是有原因的，难道还有线性做法???
是这样没错
考虑$K=max{F_j}(jin [i-R,i-L])$，一定会有$F_iin{K-1,K,K+1}$。
因此有一个显然的结论是$F_i$可能从$j$处转移当且仅当$F_j=K-1$或$F_j=K$。
考虑对于每一个$F_j$维护一个元素为关于$j$的单调队列，队列内元素保证有队首到队尾$S_j$依次递增且$jin [i-R,i-L]$，再维护一个单调队列求的$max{F_j}(jin [i-R,i-L])$，每次从$F_j=K-1$或$F_j=K$转移即可。
时间复杂度$O(n)$。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define M 1001000
using namespace std;
int read(){
int nm=0,fh=1; int cw=getchar();
for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
int F[M],n,m,fs[M<<1],fin[M<<1],last[M<<1],nt[M<<1],L,R,t[M],q[M],hd=1,tl=1;
void ins(int ps,int x){
if(F[x]<-n) return;
while(fin[ps]>=0&&t[fin[ps]]>t[x]) fin[ps]=last[fin[ps]];
if(fin[ps]==-1) fs[ps]=fin[ps]=x,last[x]=-1;
else nt[fin[ps]]=x,last[x]=fin[ps],fin[ps]=x; nt[fin[ps]]=-1;
}
void del(int ps,int x){
if(fs[ps]!=x) return; fs[ps]=nt[fs[ps]],last[fs[ps]]=-1;
if(fin[ps]==x) fin[ps]=fs[ps],nt[fin[ps]]=-1;
}
int main(){
n=read(),L=read(),R=read();
memset(fs,-1,sizeof(fs)),memset(fin,-1,sizeof(fin));
for(int i=1;i<=n;i++){
int res; t[i]=read()+t[i-1],F[i]=-(M<<1);
if(i<L) continue; ins(F[i-L]+M,i-L);
if(i>R) del(F[i-R-1]+M,i-R-1);
while(q[hd]<i-R) hd++;
while(hd<=tl&&F[q[tl]]<=F[i-L]) tl--;
q[++tl]=i-L,m=F[q[hd]];
if(fs[m+M]>=0) F[i]=max(F[i],F[fs[m+M]]+(t[i]>t[fs[m+M]])-(t[i]<t[fs[m+M]])); m--;
if(fs[m+M]>=0) F[i]=max(F[i],F[fs[m+M]]+(t[i]>t[fs[m+M]])-(t[i]<t[fs[m+M]]));
}
if(F[n]<-n) puts("Impossible");
else printf("%d
",F[n]); return 0;
}
手懒党表示用优秀的卡常技巧卡过去就已经很满足了。