atcoder 上错 $19,20$ 两个点。

思路是把问题分为几个独立的子区间，每个子区间里面，用 std::set 维护存活的区间及其概率，可以知道 set 内的区间无交集，按坐标排序分成子问题后，按时间进行模拟。

每一次的操作：

1.更新时间 $i$ 的答案为 $a_i$ 电线杆倒塌让 $a_i$ 所在区间全部倒塌的概率乘上剩余区间全部倒塌概率。

2.更新时间 $i$ 以前 $a_i$ 所在区间全部倒塌的概率。

由于使用了很多自己写的 library，代码看起来很逆天，求条。。。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cassert>
#include <numeric>
#include <limits>
#include <set>
#define mp make_pair
#pragma GCC diagnostic ignored "-Wunused-parameter"

using namespace std;

typedef long long LL;

constexpr int N = 200010;
constexpr int mod = 998244353;
inline LL quick_pow(LL base, LL ind)
{
  LL res = 1;
  base %= mod;
  for (; ind; ind >>= 1)
  {
    if (ind & 1ll)
    {
      res = res * base % mod;
    }
    base = base * base % mod;
  }
  return res;
}

template <typename T> // fs 结构题在分母不出现 0 的前提下可以少一个 log
struct fs
{
  T fz, fm;
  fs(T _fz, T _fm)
  {
    fz = (_fz % mod + mod) % mod, fm = (_fm % mod + mod) % mod;
    assert(fm && fz >= 0 && fm >= 0);
  }
  fs(T num)
  {
    fz = num % mod;
    fm = 1ll;
  }
  fs()
  {
    fz = 0;
    fm = 1ll;
  }
  operator bool() const { return fz != 0ll; }
  fs operator+(const fs &Q) const
  {
    return fs(fz * Q.fm + fm * Q.fz, fm * Q.fm);
  }
  inline fs &operator+=(const fs &Q) { return *this = *this + Q; }
  fs operator-(const fs &Q) const
  {
    return fs(fz * Q.fm % mod - fm * Q.fz % mod, fm * Q.fm % mod);
  }
  inline fs &operator-=(const fs &Q) { return *this = *this - Q; }
  fs operator*(const fs &Q) const
  {
    return fs(fz * Q.fz % mod, fm * Q.fm % mod);
  }
  inline fs &operator*=(const fs &Q) { return *this = *this * Q; }
  fs operator/(const fs &Q) const
  {
    return *this * fs(Q.fm, Q.fz);
  }
  inline fs &operator/=(const fs &Q) { return *this = *this / Q; }
  static void exgcd(T a, T b, T &x, T &y)
  {
    if (b == 0)
    {
      x = 1;
      y = 0;
      return;
    }
    exgcd(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - a / b * x;
    return;
  }
  void print(std::ostream &os)
  {
    os << fz << '/' << fm << '\n';
  }
  friend ostream &operator<<(ostream &os, const fs Q)
  {
    T x, y;
    exgcd(Q.fm % mod, mod, x, y);
    return os << (x * (Q.fz % mod) % mod + mod) % mod, os;
  }
  friend std::istream &operator>>(std::istream &is, fs &Q)
  {
    return is >> Q.fz >> Q.fm, is;
  }
  bool operator==(const fs &Q) const
  {
    return fz * Q.fm == fm * Q.fz;
  }
  bool operator<(const fs &Q) const { return false; }
};

int n, m, a[N], id[N];
int cnt{1}, pos[N];

vector<int> bl[N];

template <typename T>
struct range
{
  typedef range<T> this_type;

  range(T _l = std::numeric_limits<T>::min(), T _r = std::numeric_limits<T>::max())
      : l(_l), r(_r) {}

  bool operator<(const range &Q) const { return r < Q.r; }
  T l, r;

  template <typename val_t>
  inline bool is_in(const val_t &val) { return l <= val && val <= r; }

  inline bool empty() const
  {
    if (r < l)
      return true;
    else
      return false;
  }

  inline this_type operator+(const this_type &Q) const
  {
    if (empty() && Q.empty())
      return range<T>(1, 0);
    else if (empty())
      return Q;
    else if (Q.empty())
      return *this;
    return range(std::min(l, Q.l), std::max(r, Q.r));
  }
  inline this_type &operator+=(const this_type &Q)
  {
    return *this = *this + Q;
  }
  inline this_type operator*(const this_type &Q) const
  {
    if (empty() || Q.empty())
      return range<T>(1, 0);
    return range(std::max(l, Q.l), std::min(r, Q.r));
  }
  inline this_type &operator*=(const this_type &Q)
  {
    return *this = *this * Q;
  }

  inline friend std::ostream &operator<<(std::ostream &os, const this_type Q)
  {
    return os << '[' << Q.l << ", " << Q.r << ']';
  }
};

fs<LL> p[N], ans[N];
int pos1[N];
fs<LL> prod = 1ll;
int tt = 0;
int vis[N];

set<pair<range<int>, fs<LL>>> blp[N];

void solve(int nm, int apos) // nm 块名, apos 更新的地方的名字
{
  fs<LL> res = 0;

  const int ml = 1, mr = bl[nm].size();
  const int kk = pos1[apos];

  auto it = blp[nm].lower_bound(mp(range<int>(0, kk), fs<LL>()));

  assert(it != blp[nm].end());                            // 断言成功
  assert(range<int>(it->first.l, it->first.r).is_in(kk)); // 断言成功

  int l = it->first.l, r = it->first.r;
  fs<LL> ptm = it->second;

  blp[nm].erase(it); // range 乘法返回两区间交集

  if (!((range<int>(kk + 1, mr) * range<int>(l, r)).empty())) // 向左倒
    blp[nm].insert(mp(range<int>(kk + 1, mr) * range<int>(l, r), ptm / fs(2ll)));
  else
    res += ptm / fs(2ll);

  if (!((range<int>(ml, kk - 1) * range<int>(l, r)).empty())) // 向右倒
    blp[nm].insert(mp(range<int>(ml, kk - 1) * range<int>(l, r), ptm / fs(2ll)));
  else
    res += ptm / fs(2ll);

  if (tt == cnt && p[nm])
    prod /= p[nm];
  p[nm] += res;

  if (!vis[nm] && p[nm])
  {
    vis[nm] = 1;
    tt++;

    if (tt == cnt) // 所有地方都可能倒
    {
      bool flag = true; // 如果有 0 的话会出问题。。。
      prod = fs(1ll, 1ll);
      for (int i = 1; i <= cnt; i++)
      {
        if (p[i])
          prod *= p[i];
        else
          flag = false;
      }
      if (flag)
        ans[apos] = prod;
      return;
    }
  }

  if (tt == cnt)
    ans[apos] = prod * res; // 更新答案
  if (p[nm] && tt == cnt)
    prod *= p[nm]; // 更新概率乘积
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  // freopen("in.txt", "r", stdin);
  // freopen("my.txt", "w", stdout);

  cin >> n >> m;

  for (int i = 1; i <= n; i++)
    cin >> a[i], id[i] = i;

  sort(id + 1, id + n + 1, [](const int A, const int B)
       { return a[A] < a[B]; });

  bl[1].push_back(id[1]); // 块内名字按坐标排序
  pos[id[1]] = pos1[id[1]] = 1;

  for (int i = 2; i <= n; i++)
  {
    if (a[id[i]] - a[bl[cnt].back()] > m)
      bl[++cnt].push_back(id[i]);
    else
      bl[cnt].push_back(id[i]);
    pos[id[i]] = cnt;
    pos1[id[i]] = bl[cnt].size();
  }

  for (int i = 1; i <= cnt; i++)
    blp[i].insert(mp(range<int>(1, (int)bl[i].size()), fs<LL>(1)));

  for (int i = 1; i <= n; i++) // 按时间 solve
    solve(pos[i], i);

  const fs<LL> inv = fs<LL>(quick_pow(2, n), 1ll);

  for (int i = 1; i <= n; i++)
    cout << ans[i] * inv << ' ';

  return 0;
}