競プロ日記

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

template <long long mod_num>
class ModInt {
  long long x;

  public:
  constexpr ModInt(const long long num = 0) : x(num % mod_num) { if (x < 0) x += mod_num; }
  constexpr bool   operator==(const ModInt &r) const { return this->x == r.x; }
  constexpr bool   operator!=(const ModInt &r) const { return this->x != r.x; }
  constexpr bool   operator<(const ModInt &r) const { return this->x < r.x; }
  constexpr bool   operator>(const ModInt &r) const { return this->x > r.x; }
  constexpr bool   operator<=(const ModInt &r) const { return this->x <= r.x; }
  constexpr bool   operator>=(const ModInt &r) const { return this->x >= r.x; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    x += r.x;
    if (x >= mod_num) x -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (x < r.x) x += mod_num;
    x -= r.x;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    x = x * r.x % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(const ModInt &r) {
    *this *= r.inverse();
    return *this;
  }
  constexpr ModInt inverse(void) const {
    long long a = x, b = mod_num, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  constexpr ModInt pow(long long n) const { return pow(x, n); }
  static ModInt pow(long long x, long long n) {
    ModInt ret(1), mul(x);
    while (n) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n  >>= 1;
    }
    return ret;
  }
  friend istream &operator>>(istream &is, ModInt &r) {
    long long n;
    is >> n;
    r = ModInt(n);
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.x; }
  explicit operator int() const { return x; }
  explicit operator long long() const { return x; }
  explicit operator double() const { return x; }
};

template <typename T>
class SegmentTree {
  template <typename B>
  struct BinaryOperation {
    const static B unit = 0;
    B operator()(const B &a, const B &b) const { return a + b; }
  };
  BinaryOperation<T> bo;
  const T   unit;
  vector<T> tree;
  int v_size;

  public:
  SegmentTree(const int n = 0, const T unit = BinaryOperation<T>::unit) : unit(unit) { init(n); }
  SegmentTree(const vector<T> &v, const T unit = BinaryOperation<T>::unit) : unit(unit) { init(v); }
  void init(int n) {
    v_size = 1;
    while (v_size < n) v_size <<= 1;
    tree.assign(2 * v_size, unit);
  }
  void init(const vector<T> &v) {
    init(v.size());
    copy(v.begin(), v.end(), tree.end() - v_size);
    for (int i = v_size - 1; i > 0; --i) tree[i] = bo(tree[i * 2], tree[i * 2 + 1]);
  }
  void update(int i, const int x) {
    i += v_size;
    tree[i] = x;
    while (i >>= 1) tree[i] = bo(tree[i * 2], tree[i * 2 + 1]);
  }
  T query(int l, int r) const {
    T ret = unit;
    for (l += v_size, r += v_size; l < r; l = (l + 1) >> 1, r >>= 1) {
      if (l & 1) ret = bo(ret, tree[l]);
      if (r & 1) ret = bo(ret, tree[r - 1]);
    }
    return ret;
  }
  int size(void) const { return v_size; }
  T   operator[](const int i) const { return tree[i + v_size]; }
};

using mint = ModInt<998244353>;
int main(void) {
  int n;
  cin >> n;
  vector<pair<int, int>> xy(n);
  rep (i, n) cin >> xy[i].first >> xy[i].second;
  sort(all(xy));
  rep (i, n) xy[i].first = i;
  auto comp = [](pair<int, int> &a, pair<int, int> &b) { return a.second < b.second; };
  sort(all(xy), comp);
  rep (i, n) xy[i].second = i;
  vector<int> v(n, 1);
  SegmentTree<int> b(n), u(v);
  mint sum = mint::pow(2, n - 1) * n;
  rep (i, n) {
    u.update(xy[i].first, 0);
    const int  bl = b.query(0, xy[i].first), br = b.query(xy[i].first + 1, n);
    const int  ul = u.query(0, xy[i].first), ur = u.query(xy[i].first + 1, n);
    const mint bln = mint::pow(2, bl) - 1, brn = mint::pow(2, br) - 1;
    const mint uln = mint::pow(2, ul) - 1, urn = mint::pow(2, ur) - 1;
    sum += bln * urn * mint::pow(2, br + ul);
    sum += brn * uln * mint::pow(2, bl + ur);
    sum -= bln * brn * uln * urn;
    b.update(xy[i].first, 1);
  }
  cout << sum << endl;
  return 0;
}

現状での新ABC最終問題にして、初実装をいくつか経験させてもらえてとてもためになった問題。
考察部分では、各点ごとに何回含まれるかを考えれば良さそうというところまでは思いつけた。
頭が固くてそこから先には進めなかった。
解説を見たらあまりにそりゃそうだ感があって拍子抜けしてしまった。
座標圧縮の必要性はいまいち感じなかったのだが、セグメントツリーに乗せてなるほどとなった。

今回大きく経験になったポイントが3つ！

・包除原理
内容は知っていたが問題としては初。
ベン図的な表現なら分かりやすいのだが、何通りを求める問題だと何が論理積なのか一瞬迷った。
何通りかを考えるなら論理積は掛け算になるはずなので、今見ている点の左上に位置する点から1つ以上選ぶ選び方をA、右上をB、左下をC、右下をDとすると、A*C+B*D-A*B*C*Dとなるはずである。
しかしこれだとA*B*C*Dの方が大きいのでは？？？となったが、AとCの論理積ではAとC以外が二値のどちらで合っても良いので、A*CではなくA*C*(右上と左下の点の全ての選び方)が正しかった。

・座標圧縮
蟻本で眺めただけだが、内容のわりに実装難しくないか？という感想を持ったような覚えがある。
とりあえずその記憶は置いておいて、自分なりに実装してみるととても簡単だった。
被りがあったら少しややこしくなるのかなという気はするが本当に少しな気がする。

・セグメントツリーの活用
相当有名かつ汎用性の高そうなデータ構造なので、ライブラリとして実装だけはしていた。
確認用として、AOJのRMQの問題は解いているのだが、実際に問題で使うことになったのは初。
とは言っても過去にABC038 D プレゼントでBITを使っており、今回の問題もBITが使える以上セグメントツリーを使える機会としては初ではないのだが、今回はBITを使わずにセグメントツリーを使ったので事実上初である。
使い方も前回同様、数列の値のみでなくインデックスの値にも意味を持たせるもの。
やっぱりこの使い方は全然思いつけない。
調べたところ反転数を計算するときにも似たような使い方をするらしいので、反転数の問題が出てきた時はすぐに思いつきたい。


ここまで経験値になりそうな問題は初かもしれない。
なりそうだからなったかどうかは分からない。
なってると良いなぁ。