比赛 2026.1.3 评测结果 WWWWWWWWAW
题目名称 极差序列 最终得分 10
用户昵称 我常常追忆未来 运行时间 0.651 s
代码语言 C++ 内存使用 4.49 MiB
提交时间 2026-01-03 10:55:15
显示代码纯文本
#include <bits/stdc++.h>
#define int long long
const int mod=998245353; 
using namespace std;
const int N=1e6+7;
int n,k,a[N],ans;
signed main(){
	freopen("maxmin.in","r",stdin);
	freopen("maxmin.out","w",stdout);
	
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);

		for(int i=1;i<=n;i++){
			int l=1,r=n;
			int ansl,ansr;
			while(l<r){
				int mid=l+r>>1;
				if(a[mid]>=a[i]+k){
					r=mid;
				}
				else{
					l=mid+1;
				}
			}
			ansl=l;
			l=1,r=n;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(a[mid]<=a[i]+k){
					l=mid;
				}
				else{
					r=mid-1;
				}
			}
			ansr=l;
			if(a[ansl]==a[ansr]){
				if(a[ansl]==a[i]+k){
					ans=(ans+((ansl+ansr)*(ansr-ansl+1)>>1)%mod-(ansr-ansl)*i%mod)%mod;
				}
			}
		}		
	

	cout<<ans;

	return 0;
}