比赛 2026.1.3 评测结果 AAAAWAWAAA
题目名称 极差序列 最终得分 80
用户昵称 LikableP 运行时间 1.321 s
代码语言 C++ 内存使用 23.22 MiB
提交时间 2026-01-03 09:38:02
显示代码纯文本
#include <cstdio>
#include <cctype>

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

#include <algorithm>
typedef long long ll;

const int MAXN = 2e5 + 10;
const int MAXV = 1e9;
const ll MOD = 998245353;

struct NODE {
  int ls, rs;
  int sum;
} node[MAXN * 17 * 6];
int root, nodeNum;

void PushUp(int root) {
  node[root].sum = node[node[root].ls].sum + node[node[root].rs].sum;
}

void AddSingle(int &root, int lt, int rt, int pos, int val) {
  if (!root) root = ++nodeNum;
  if (lt == rt) {
    node[root].sum += val;
    return ;
  }
  int mid = lt + ((rt - lt) >> 1);
  if (pos <= mid) {
    AddSingle(node[root].ls, lt, mid, pos, val);
  } else {
    AddSingle(node[root].rs, mid + 1, rt, pos, val);
  }
  PushUp(root);
}

int GetSingle(int &root, int lt, int rt, int pos) {
  if (!root) root = ++nodeNum;
  if (lt == rt) {
    return node[root].sum;
  }
  int mid = lt + ((rt - lt) >> 1);
  if (pos <= mid) {
    return GetSingle(node[root].ls, lt, mid, pos);
  } else {
    return GetSingle(node[root].rs, mid + 1, rt, pos);
  }
}

int GetSeq(int &root, int lt, int rt, int lq, int rq) {
  if (lq > rq) return 0;
  if (!root) root = ++nodeNum;
  if (lt == lq && rt == rq) {
    return node[root].sum;
  }
  int mid = lt + ((rt - lt) >> 1);
  if (rq <= mid) {
    return GetSeq(node[root].ls, lt, mid, lq, rq);
  } else if (lq > mid) {
    return GetSeq(node[root].rs, mid + 1, rt, lq, rq);
  } else {
    return GetSeq(node[root].ls, lt, mid, lq, mid) + GetSeq(node[root].rs, mid + 1, rt, mid + 1, rq);
  }
}

int n, K;
int a[MAXN];
ll pow2[MAXN];

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("maxmin.in", "r", stdin);
    freopen("maxmin.out", "w", stdout);
  #endif
  n = read<int>(), K = read<int>();

  pow2[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pow2[i] = (pow2[i - 1] << 1) % MOD;
  }

  for (int i = 1; i <= n; ++i) {
    a[i] = read<int>();
    AddSingle(root, 1, MAXV, a[i], 1);
  }

  std::sort(a + 1, a + n + 1);

  ll ans = 0;
  for (int i = 1; i <= n && a[i] + K <= a[n]; ++i) if (a[i] != a[i - 1]) {
    int target = a[i] + K;
    ll sum1 = (pow2[GetSingle(root, 1, MAXV, target)] - 1 + MOD) % MOD;
    ll sum2 = pow2[GetSeq(root, 1, MAXV, a[i] + 1, target - 1)];
    ll sum3 = (pow2[GetSingle(root, 1, MAXV, a[i])] - 1 + MOD) % MOD;
    ans = (ans + sum1 * sum2 % MOD * sum3 % MOD) % MOD;
  }

  printf("%lld\n", ans);
  return 0;
}