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