CF1840C题解

题目描述

$T$ 组数据，每组数据给定 $n$，$k$，$q$ 和一个长度为 $n$ 的数组 $a$，求 $a$ 中长度大于等于 $k$ 且最大值小于等于 $q$ 的序列个数。
$\sum{n}\le 2e5$。

题目解析

解法一：数据结构解法

显然可以利用数据结构维护。考虑ST表预处理出区间最大值枚举区间左右端点累计，复杂度 $O(nlogn+n^2)$，需要优化。

再想想，若区间 $[i,j]$ 符合条件，则对于每个 $i\le k\le j$，区间 $[i,k]$ 都符合条件；若区间 $[i,j]$ 不符合，则对于每个 $j<k\le n$，区间 $[i,k]$ 都不符合，答案可二分。所以我们枚举左端点，二分右端点，复杂度 $O(Tnlogn)$。

解法二：数学解法

显然：一个区间符合条件，当且仅当此区间不存在一个 $i\in [i,j]$ 使 $a_i>q$。所以处理每一个 $a_i>q$ 的 $i$，统计区间长度。区间长度为 $m$ 的合法区间贡献即为 $\sum_{i=1}^{m}i$。而这个式子可以预处理，复杂度 $O(N+Tn)$。

代码实现

因为 $\sum{n}\le 2e5$，所以答案需要 long long。

解法一

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int N=2e5+10;
int T;
int n,k,q;
ll f[N][31];
inline long long maxx(int l,int r){
    int len=log(r-l+1)/log(2);
    return max(f[l][len],f[r-(1<<len)+1][len]);
}
int main(){
    scanf("%d",&T);
    while(T--){
        ll ans=0;
        scanf("%d%d%d",&n,&k,&q);
        for(int i=1;i<=n;++i) scanf("%lld",&f[i][0]);
        for(int i=1;i<=30;++i)
            for(int j=1;j+(1<<(i-1))-1<=n;++j)
                f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        for(int i=1;i+k-1<=n;++i){
            int l=i+k-1,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(maxx(i,mid)<=q) l=mid;
                else r=mid-1;
            }
            if(maxx(i,l)<=q) ans+=min(l,n)-i-k+2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

解法二

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int N=2e5+10;
int T;
int n,k,q;
ll a[N],sum[N];
int main(){
    scanf("%d",&T);
    for(int i=1;i<=N-10;++i) sum[i]=sum[i-1]+i;
    while(T--){
        ll ans=0,p=0;
        scanf("%d%d%d",&n,&k,&q);
        for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
        for(int i=1;i<=n;++i){
            if(a[i]>q){
                if(p>=k) ans+=sum[p-k+1];
                p=0;
            }
            else ++p;
        }
        if(p>=k) ans+=sum[p-k+1];
        printf("%lld\n",ans);
    }
}

完结撒花qwq