选举

也许更好的阅读体验
$Description$Description

$Solution$Solution

30分思路

设 $f\left[i\right]$f[i]表示以 $i$i结尾，划分的区间都合法时，小奇得票数比魔法猪最多多几票
设 $sum\left[i\right]$sum[i]表示支持情况的前缀和
令 $j\in \left[max\right(i-r,0),max(i-l,0\left)\right]$j∈[max(i−r,0),max(i−l,0)]
若 $sum\left[i\right]==sum\left[j\right]$sum[i]==sum[j] 则 $f\left[i\right]=max\left(f\right[i],f[j\left]\right)$f[i]=max(f[i],f[j])
若 $sum\left[i\right]\>sum\left[j\right]$sum[i]  > sum[j] 则 $f\left[i\right]=max\left(f\right[i],f[j]+1)$f[i]=max(f[i],f[j]+1)
若 $sum\left[i\right]\&lt;sum\left[j\right]$sum[i]  < sum[j] 则 $f\left[i\right]=max\left(f\right[i],f[j]-1)$f[i]=max(f[i],f[j]−1)
复杂度 $O(n\ast (r-l+1\left)\right)$O(n∗(r−l+1))
代码就不贴了

100分思路

考虑优化30分思路，能否用数据结构把 $(r-l+1)$(r−l+1)的复杂度优化为 $log$log级别
用一个权值线段树来维护每一个 $sum$sum值，即权值线段树中的节点的意义为，若该节点表示区间 $[k,k]$[k,k](叶子节点),它维护的值是在当前计算的位置的合法区间 $\left[max\right(i-r,0),max(i-l,0\left)\right]$[max(i−r,0),max(i−l,0)]内， $sum$sum值为 $k$k的数的 $f$f最大是多少
这样我们只要动态地维护权值线段树就可以了，而每当 $i$i往后移一次，实质上有效区间就是整体往后移了一位，要维护的就只有区间两端的数字，用优先队列维护 $sum$sum的最大 $f$f值即可
代码

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年06月22日 星期六 08时06分50秒 *******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
#define mk make_pair
using namespace std;
const int maxn = 1000006;
const int m = 1000001;
const int inf = 10000007;
const char no [] = "Impossible";
//{{{cin 读入优化
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,l,r;
int sum[maxn],f[maxn];
int val[maxn<<3],pos[maxn<<1],lt[maxn<<3],rt[maxn<<3];
priority_queue < pair<int,int> > q[maxn<<1];
//{{{build(k,l,r)
void build (int k,int l,int r)
{
	lt[k]=l,rt[k]=r;
	if (l==r){
		val[k]=-inf,pos[l]=k;
		return ;
	}
	int mid=(l+r)>>1;
	build (k<<1,l,mid);
	build (k<<1|1,mid+1,r);
	val[k]=max(val[k<<1],val[k<<1|1]);
}
//}}}
//{{{insert(u,v)
void insert (int u,int v)
{
	int k=pos[u];
	while (k){
		val[k]=max(val[k],v);
		k>>=1;
	}
}
//}}}
//{{{change(u,v)
void change (int u,int v)
{
	int k=pos[u];
	val[k]=v;
	while (k>>=1)	val[k]=max(val[k<<1],val[k<<1|1]);
}
//}}}
//{{{query(k,l,r)
int query (int k,int l,int r)
{
	if (lt[k]>=l&&rt[k]<=r)	return val[k];
	if (lt[k]>r||rt[k]<l)	return -inf;
	int res=-inf;
	res=max(res,query(k<<1,l,r));
	res=max(res,query(k<<1|1,l,r));
	return res;
}
//}}}
int main()
{
	cin>>n>>l>>r;
	for (int i=1;i<=n;++i)	cin>>sum[i],sum[i]+=sum[i-1];
	build(1,1,m<<1);
	for (int i=1;i<=n;++i)	f[i]=-inf;
	f[0]=0,q[0].push(mk(0,0));//二元组(f,k)表示f值和位置
	for (int i=l;i<=n;++i){
		int s=sum[i-l]+m;//防止负数
		insert(s,f[i-l]);
		q[s].push(mk(f[i-l],i-l));
		if (i>r){
			s=sum[i-r-1]+m;
			while (!q[s].empty()&&i-r>q[s].top().second)	q[s].pop();
			if(q[s].empty())	change(s,-inf);
			else	change(s,q[s].top().first);
		}
		s=sum[i]+m;
		f[i]=max(f[i],query(1,1,s-1)+1);
		f[i]=max(f[i],query(1,s,s));
		f[i]=max(f[i],query(1,s+1,m<<1)-1);
	}
	if (f[n]<-n)	printf("%s\n",no);
	else	printf("%d\n",f[n]);
	return 0;
}