Manthan, Codefest 18 (rated, Div. 1 + Div. 2) F 单调栈 + 贡献 + 计数

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;

}