题解：CF1833F Ira and Flamenco

蒟 / 2024-07-16 / 原文

思路

因为要一个长度为 $m$ 的，且最大与最小的元素之差小于等于 $m$ 所以序列应为 $a_i，a_i+1,a_i+2\dots,a_i+m-1$，所以满足要求的序列之需要连续 $m$ 个就行了，这个最开始排序，去重后用 lower_bound 求一下小于 $a_i+m-1$ 的数有没有 $m$ 个就行了。

考虑满足要求序列的答案，每个值相同的数只选一次且必须选一次，我们设 $mp_{a_i}$ 为值为 $a_i$ 的数的个数，所以 $ans=mp_{a_i}\times mp_{a_i+1}\dots\times mp_{a_i+m-1}$ 这一坨要用线段树不然会超 long long，把每个答案贡献记在满足要求的序列中的最小的 $a_i$ 上就行了。

代码

#include<bits/stdc++.h>
#define int long long
#define mid (tr[x].l+tr[x].r>>1)
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int T,n,m,ans;

map <int,int> mp;

int a[N],b[N],sum,cnt[N];

struct node {
	int ad,l,r;
} tr[N<<2];

void pushup(int x) {
	return void(tr[x].ad=(tr[x<<1].ad*tr[x<<1|1].ad)%mod);
}

void build(int x,int l,int r) {
	tr[x].l = l, tr[x].r = r;
	if(l==r) return void(tr[x].ad = cnt[l]);
	build(x<<1,l,mid),build(x<<1|1,mid+1,r);
	return void(pushup(x));
}

int query(int x,int L,int R) {
//	cout<<tr[x].ad<<" ";
	if(tr[x].l>=L&&tr[x].r<=R) return tr[x].ad;
	int anss = 1;
	if(L<=mid) anss*=query(x<<1,L,R);
	anss%=mod;
	if(R>mid) anss*=query(x<<1|1,L,R);
	return anss%mod;
}

signed main() {
//	freopen("neat.in","r",stdin);
//	freopen("neat.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin>>T;
	int p,k;
	while(T--) {
		cin>>n>>m;
		ans = 0;
		for(int i=1; i<=n; ++i) {
			cin>>a[i];
			mp[a[i]]++;
		}
		sort(a+1,a+1+n);
		for(int i=1; i<=n; ++i) b[i] = a[i];
		p = unique(b+1,b+1+n)-b-1;
		if(m>p) {
			cout<<"0\n";
			for(int i=1; i<=n; ++i) mp[a[i]] = 0;
			continue;
		}
		for(int i=1; i<=p; ++i) cnt[i] = mp[b[i]];
		build(1,1,p);
		for(int i=1; i<=p; ++i) {
			k = lower_bound(b+1,b+1+p,b[i]+m) - b - 1;
			if(k-i+1<m) continue;
			ans += query(1,i,k);
			ans%=mod;
		}
		for(int i=1; i<=n; ++i) mp[a[i]] = 0;
		cout<<ans<<'\n';
	}
	return 0;
}