2019南昌G
模数为合数,所以只有约3000个数字不为0
记录一下不为0的数字位置
H[x]代表距离为x的连续段的数字和的最大值
处理出H[x]
再H[x] = max(H[x],H[x-1])记录下前缀最大,
对每个询问二分答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int A[];
const int mod = ;
void init()
{
A[]=;
for(int i=;i<=;i++){
A[i]=(A[i-]*i)%mod;
}
}
int x;
vector<int>v;
int B[];
int H[];
int pre[];
signed main()
{
init();
scanf("%lld%lld",&n,&q);
v.push_back();
for(int i=;i<=n;i++){
scanf("%lld",&x);
if(x<=){
B[i]=A[x];
v.push_back(i);
}else{
B[i]=;
}
} for(int j=;j<v.size();j++){
pre[j]=(B[v[j]]+pre[j-])%mod;
}
for(int i=;i<=v.size();i++){
for(int j=;j+i-<v.size();j++){
H[v[j+i-]-v[j]+]=max(H[v[j+i-]-v[j]+],(pre[j+i-]-pre[j-]+mod)%mod);
}
}
for(int i=;i<=n;i++){
H[i]=max(H[i],H[i-]);
}
for(int i=;i<=q;i++){
scanf("%lld",&x);
int l = ,r =n+;
while(l+<=r){
int mid=(l+r)/;
if(H[mid]<x){
l= mid+;
}else r=mid;
}
if(l==n+){
cout<<-<<'\n';
}else{
cout<<l<<'\n';
}
}
}