题意
给出长度为n的序列，只有1,0,-1。要求将其划分为若干长度在[L,R]之间的连续序列，一个序列若和大于0，造成1的贡献；若小于0，造成-1的贡献；否则没有贡献。求最大的贡献。
时间复杂度要求nlogn。
思考
线段树维护即可。以造成1的贡献为例。设当前前缀和为sumi，则需要在[max(0,i-R),i-L]中找到最大的f。以sum为下标，建立权值线段树，在叶子节点处维护单调队列即可。
需要注意的是，在上述范围中的f可能是不合法的（如i=4，l=r=3时，f1是无意义的），要将其赋值为-inf。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1E6+5; 4 const int inf=10000001; 5 int n,a[maxn],sum[maxn],x,f[maxn],L,R,t[maxn*4],ans[maxn*4],head[maxn*4],where[maxn]; 6 int base=INT_MAX; 7 bool yes[maxn]; 8 struct pt 9 { 10 int num,x; 11 }; 12 vector<pt>q[maxn*4]; 13 void update(int num) 14 { 15 ans[num]=max(ans[num<<1],ans[num<<1|1]); 16 } 17 void add(int l,int r,int pos,int x,int y,int num) 18 { 19 if(l==r) 20 { 21 while(head[num]<=int(q[num].size()-1)&&q[num][q[num].size()-1].x<=x) 22 { 23 yes[q[num][q[num].size()-1].num]=1; 24 q[num].pop_back(); 25 } 26 q[num].push_back((pt){y,x}); 27 ans[num]=q[num][head[num]].x; 28 return; 29 } 30 int mid=(l+r)>>1; 31 if(pos<=mid)add(l,mid,pos,x,y,num<<1); 32 else add(mid+1,r,pos,x,y,num<<1|1); 33 update(num); 34 } 35 void remove(int l,int r,int pos,int y,int num) 36 { 37 if(l==r) 38 { 39 // cout<<head[num]<<" "<<q[num].size()<<endl 40 if(head[num]>int(q[num].size())-1)return; 41 if(q[num][head[num]].num!=y)return; 42 if(head[num]<=int(q[num].size())-1&&!yes[q[num][head[num]].num]) 43 { 44 yes[q[num][head[num]].num]=1; 45 ++head[num]; 46 } 47 if(head[num]<=int(q[num].size())-1)ans[num]=q[num][head[num]].x; 48 else ans[num]=-inf; 49 return; 50 } 51 int mid=(l+r)>>1; 52 if(pos<=mid)remove(l,mid,pos,y,num<<1); 53 else remove(mid+1,r,pos,y,num<<1|1); 54 update(num); 55 } 56 int ask(int L,int R,int l,int r,int num) 57 { 58 if(L<=l&&r<=R)return ans[num]; 59 int mid=(l+r)>>1; 60 if(R<=mid)return ask(L,R,l,mid,num<<1); 61 else if(mid<L)return ask(L,R,mid+1,r,num<<1|1); 62 else return max(ask(L,R,l,mid,num<<1),ask(L,R,mid+1,r,num<<1|1)); 63 } 64 int main() 65 { 66 ios::sync_with_stdio(false); 67 cin>>n>>L>>R; 68 for(int i=1;i<=n;++i) 69 add(1,n,i,-inf,0,1); 70 for(int i=1;i<=n;++i) 71 { 72 cin>>x; 73 sum[i]=sum[i-1]+x; 74 base=min(base,sum[i]); 75 } 76 for(int i=1;i<=n;++i) 77 f[i]=-inf; 78 base=-base+1; 79 for(int i=L;i<=R;++i) 80 { 81 if(sum[i]>0)f[i]=1; 82 else if(sum[i]<0)f[i]=-1; 83 else f[i]=0; 84 } 85 for(int i=L;i<=n;++i) 86 { 87 int p; 88 if(sum[i]+base-1>=1) 89 { 90 p=ask(1,sum[i]+base-1,1,n,1); 91 f[i]=max(f[i],p+1); 92 } 93 if(sum[i]+base+1<=n) 94 { 95 p=ask(sum[i]+base+1,n,1,n,1); 96 f[i]=max(f[i],p-1); 97 } 98 p=ask(sum[i]+base,sum[i]+base,1,n,1); 99 f[i]=max(f[i],p); 100 if(i-L+1>=L) 101 add(1,n,sum[i-L+1]+base,f[i-L+1],i-L+1,1); 102 if(i-R>=L) 103 remove(1,n,sum[i-R]+base,i-R,1); 104 } 105 if(f[n]<=-5000000)cout<<"IMPOSSIBLE"<<endl; 106 else cout<<f[n]<<endl; 107 return 0; 108 }