Submission #6798138

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

template <std::uint64_t M>
class modint {
 public:
  uint64_t a;

  explicit constexpr modint(const uint64_t x = 0) noexcept : a(x % M) {}
  constexpr uint64_t &value() noexcept { return a; }
  constexpr const uint64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    uint64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<998244353>;

template <typename T>
class SegTree {
 private:
    int _n;
    T _init_val;
    std::vector<T> _data;
    std::function<T(T, T)> _f;

    T _query(int a, int b, int k, int l, int r) {
        // [a b)と[l r]が交差しない
        if (r <= a || b <= l) return _init_val;

        // [a b)が[l r]を含む
        if (a <= l && r <= b) return _data[k];

        T vl = _query(a, b, k*2+1, l, (l+r)/2);
        T vr = _query(a, b, k*2+2, (l+r)/2, r);

        return _f(vl, vr);
    }

 public:
    SegTree(int n, T init_val, std::function<T(T, T)> f) {
        _init_val = init_val;
        _n = 1;
        _f = f;

        while (_n < n)
            _n *= 2;
        _data.resize(2 * _n, init_val);
    }

    T get(int k) {
        return _data[k + _n - 1];
    }

    void update(int k, T a) {
        k += _n-1;
        _data[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            _data[k] = _f(_data[k*2+1], _data[k*2+2]);
        }
    }

    // [a b)の範囲でfを適用
    T query(int a, int b) {
        return _query(a, b, 0, 0, _n);
    }

    // 先頭からチェックし，はじめてxを満たしたインデックス
    int lower_bound(T x) {
        return _lower_bound(x, 0);
    }

    int _lower_bound(T x, int k) {
        if (k >= _n-1) {
            return k - (_n - 1);  // 葉
        } else if (_data[k] < x) {
            return _n;  // 該当なし
        } else if (x <= _data[k * 2 + 1]) {
            return _lower_bound(x, k * 2 + 1);
        } else {
            return _lower_bound(x - _data[k * 2 + 1] , k * 2 + 2);
        }
    }
};

mint pow2(ll n) {
  if (n==0) {
    return mint(1);
  } else if (n%2 == 0) {
    auto x = pow2(n/2);
    return x * x;
  } else {
    return pow2(n-1) * mint(2);
  }
}

signed main() {
  ll N;
  cin>>N;

  vector<PLL> p(N); // {x,y}
  rep(i,N)
    cin >> p[i].first >> p[i].second;

  sort(begin(p), end(p));

  // Y座標を圧縮 0 <= y <= 200000
  {
    set<ll> ys;
    rep(i,N)
      ys.insert(p[i].second);
    ll i = 0;
    map<ll,ll> mp;
    for (auto y: ys){
      mp[y] = i++;
    }
    rep(i,N)
      p[i].second = mp[p[i].second];
  }

  vector<ll> a(N), b(N), c(N), d(N); // a[i]: i番目のときに領域Aに含まれる点の数
  {
    SegTree<ll> st(200010, 0, [](ll x, ll y){ return x+y; });
    rep(i,N){
      c[i] = st.query(0, p[i].second);
      a[i] = st.query(p[i].second, 200010);
      st.update(p[i].second, 1);
    }
  }
  {
    SegTree<ll> st(200010, 0, [](ll x, ll y){ return x+y; });
    for (int i=N-1; i>=0; i--) {
      d[i] = st.query(0, p[i].second);
      b[i] = st.query(p[i].second, 200010);
      st.update(p[i].second, 1);
    }
  }
  //rep(i,N){
  //  printf("a[%d]=%d c[%d]=%d b[%d]=%d d[%d]=%d\n", i, a[i], i, c[i], i, b[i], i, d[i]);
  //}

  mint ans(0);
  rep(i,N) {
    // 1. 点iを含まない場合
    // e[a-d]: 各領域に1個以上の要素を含めるかどうか
    rep(ea, 2) rep(eb, 2) rep(ec, 2) rep(ed, 2) {
      if ((ea|ec) & (eb|ed) & (ea|eb) & (ec|ed)) {
        mint t(1);
        if (ea) t *= pow2(a[i])-mint(1);
        if (eb) t *= pow2(b[i])-mint(1);
        if (ec) t *= pow2(c[i])-mint(1);
        if (ed) t *= pow2(d[i])-mint(1);
        ans += t;
      }
    }

    // 2. 点iを含む場合
    ans += pow2(a[i]) * pow2(b[i]) * pow2(c[i]) * pow2(d[i]);
  }
  cout << ans.value() << endl;
  return 0;
}

Submission Info

Judge Result