https://codeforces.com/contest/1037/problem/F
题意
function z(array a, integer k):
if length(a) < k:
return 0
else:
b = empty array
ans = 0
for i = 0 .. (length(a) - k):
temp = a[i]
for j = i .. (i + k - 1):
temp = max(temp, a[j])
append temp to the end of b
ans = ans + temp
return ans + z(b, k)
题解
- 实际上数组每次只是减少k-1
- 计算贡献,每k个数最后只能剩下最大那个数,所以对于a[i]我们需要计算最后剩下a[i]的情况数*a[i]就是a[i]的贡献,对于每个a[i]的情况数是他作为第一个最大的元素的区间数
- 用单调栈维护左边第一个\(\geq a[i]\),右边第一个\(> a[i]\)的数
- 设cal(l,r)计算区间(l,r)的情况数,则包含a[i]的情况数等于cal(l,r)-cal(l,i-1)-cal(i+1,r)
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P=1e9+7;
const int MAXN=1e6+5;
ll n,k;
int S[MAXN],t,a[MAXN],L[MAXN],R[MAXN];
ll cal(ll x){
if(x<k)return 0;
ll Element=(x-k+1)/(k-1);
ll Fst=x-k+1-(k-1)*Element,Lst=x-k+1;
return (Lst+Fst)*(Element+1)/2%P;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
while(t>0&&a[S[t-1]]<a[i])t--;
if(t==0)L[i]=0;
else L[i]=S[t-1];
S[t++]=i;
}
t=0;
for(int i=n;i>=1;i--){
while(t>0&&a[S[t-1]]<=a[i])t--;
if(t==0)R[i]=n+1;
else R[i]=S[t-1];
S[t++]=i;
}
ll ans=0;
for(int i=1;i<=n;i++){
ll tp=0;
L[i]++;R[i]--;
tp+=cal(R[i]-L[i]+1);tp%=P;
tp-=cal(i-L[i]);tp=(tp+P)%P;
tp-=cal(R[i]-i);tp=(tp+P)%P;
ans=(ans+tp*a[i]%P)%P;
}
cout<<ans<<endl;
}