G.Eating Plan
题意
给出长度为n<1e5的排列p(1到n都只出现一次)
m<1e4次询问，每次输入一个数k
求一个最短区间[L,R]的长度
使得$∑_{i=L}^R p[i]! $ $mod$ $998857459 >=k$
题解
参考题解
打表发现当p[i]>=2803时 p[i] mod 998857459 为0
因为实际上模数 998857459 并不是一个素数
所以当n大于2803时，实际上只有 2802个 p[i]需要计算
于是存入2802×2802个区间 根据pair<区间和,区间长度> 升序排列
在每次二分查找一个区间和>=k的下标pos
由于优先以区间和升序排列 区间长度没有准确的递增递减趋势
所以预处理出一个后缀数组suff[i]表示后往前到下标为i的所有区间中长度最短的值
答案输出suff[pos] 若不存在则输出-1
对于每次询问k，首先需要找到存在一个区间的和($∑_{i=L}^R p[i]! $)>=k
显然每个区间长度下只有最大的区间和($∑_{i=L}^R p[i]! $) 才是有用的信息 其他的均可抛弃
其次我们需要找到 相同区间和的情况下最短的区间长度
那么显然只有2802×2802个区间有用
假如有p[i]! mod 998857459 如下：
0 0 5 0 1 0 2
我们选择区间和=6的区间会选择[3,5]而不将0纳入
因为[2,5]和[3,5]区间和都为6但是显然[3,5]长度更短
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=5e5+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
ll P[Max],pos[Max];
int main(){
ll n;cin>>n;
for(int i=1;i<=n;i++){
cin>>P[i];
pos[P[i]]=i;
}
ll ans=1ll*pos[1]*(pos[1]-1)/2+1ll*(1+n-pos[1])*(n-pos[1])/2;
if(n>=2&&pos[2]>pos[1])ans+=1ll*(pos[2]-pos[1])*(pos[1])*2;
else if(n>=2&&pos[2]<pos[1])ans+=1ll*(pos[1]-pos[2])*(n-pos[1]+1)*2;
ll rightpos=max(pos[1],pos[2]),leftpos=min(pos[1],pos[2]);
for(int i=3;i<=n;i++){
if(pos[i]<leftpos){
ans+=1ll*(n-rightpos+1)*(leftpos-pos[i])*i;
}
else if(pos[i]>rightpos){
ans+=1ll*leftpos*(pos[i]-rightpos)*i;
}
rightpos=max(rightpos,pos[i]);
leftpos=min(leftpos,pos[i]);
}
ans+=n+1;
cout<<ans<<endl;
}
|