题意
https://codeforces.com/contest/1037/problem/F
思考
摘自一种比较有趣的做法。我们对序列进行分治，每次统计跨过mid的区间的贡献。其正确性是保证的：每个区间只会对应到一个mid。对于左区间，算出它的后缀最大值。
接下来从左到右枚举右区间的每一个点。对于点$i$，右端点在它上面的区间的跨度是$k-1$的。因此除了最大值相同的从右到左的block个区间，剩下的贡献要通过左区间跨度为(k-1)的（后缀最大值）的前缀和求出。
代码很少，但细节很多。虽然复杂度为$O(nlogn)$，但不失为解决这一类问题的优秀算法。
代码
1 #include<bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long int ll; 5 const int maxn=1E6+5; 6 int n,k; 7 ll ans,a[maxn],maxx[maxn],sum[maxn]; 8 inline ll max(ll x,ll y) 9 { 10 return x>y?x:y; 11 } 12 void solve(int l,int r) 13 { 14 if(r-l+1<k) 15 return; 16 int mid=(l+r)>>1; 17 maxx[mid]=a[mid]; 18 for(int i=mid-1;i>=l;--i) 19 maxx[i]=max(maxx[i+1],a[i]); 20 sum[l-1]=0; 21 sum[l]=maxx[l]; 22 for(int i=l+1;i<=mid;++i) 23 { 24 sum[i]=0; 25 int pos=i-k+1; 26 if(pos>=l) 27 sum[i]=sum[pos]; 28 sum[i]=(sum[i]+maxx[i])%mod; 29 } 30 ll now=a[mid+1]; 31 for(int i=mid+1,j=mid;i<=r;++i,now=max(now,a[i])) 32 { 33 if(i-l+1<k) 34 continue; 35 while(j>=l&&maxx[j]<now) 36 --j; 37 int len=i-j+1; 38 int block=(len-2)/(k-1); 39 int out=block+1; 40 block-=(i-mid-1)/(k-1); 41 ans=(ans+block*now%mod+sum[max(l-1,i-out*(k-1))])%mod; 42 } 43 solve(l,mid),solve(mid+1,r); 44 } 45 int main() 46 { 47 ios::sync_with_stdio(false); 48 cin>>n>>k; 49 for(int i=1;i<=n;++i) 50 cin>>a[i]; 51 solve(1,n); 52 cout<<ans<<endl; 53 return 0; 54 }