#321436 (C++14) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: yuppe19 😺
• 提出日時: 2019-03-07 12:14:19
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 462 ms / 1,000 ms
• コード長: 6,100 bytes
• コンパイル時間: 1,118 ms
• コンパイル使用メモリ: 91,420 KB
• 実行使用メモリ: 13,844 KB
• 最終ジャッジ日時: 2024-06-23 14:48:10
• 合計ジャッジ時間: 5,056 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
other	AC * 15

ソースコード

#include <iostream>
#include <tuple>
#include <vector>
using namespace std;
using i64 = int64_t;
using u32 = uint32_t;

void debug(const vector<int> &v) {
  for(size_t i=0, n=v.size(); i<n; ++i) {
    if(i) { fprintf(stderr, " "); }
    fprintf(stderr, "%d", v[i]);
  }
  fprintf(stderr, "\n");
}

u32 uy = u32(time(NULL));
u32 xorshift32() {
  uy ^= uy << 14;
  uy ^= uy >> 13;
  uy ^= uy << 15;
  return uy;
}

template <typename T>
bool __attribute__((noinline)) is_null(T* obj) { return obj == nullptr; }

// RBST (Randomised Binary Search Tree)
template <class T>
struct RBST {
  struct Node { // {{{ Node
    constexpr static T nullval = -1; // valueAt() で不正な場所が指定されたときに返す値.
    T val;
    int treeSize;
    Node *lo, *hi;

    explicit Node(T _val) : val(_val), treeSize(1), lo(nullptr), hi(nullptr) {}

    int size() {
      if(is_null(this)) { return 0; }
      return treeSize;
    }

    Node* update() {
      treeSize = lo->size() + hi->size() + 1;
      return this;
    }

    static Node* merge(Node *l, Node *r) {
      if(is_null(l)) { return r; }
      if(is_null(r)) { return l; }
      size_t lSize = l->size(),
             rSize = r->size();
      if(xorshift32() % (lSize + rSize) < lSize) {
        l->hi = merge(l->hi, r);
        return l->update();
      } else {
        r->lo = merge(l, r->lo);
        return r->update();
      }
    }

    pair<Node*, Node*> split(int k) { // [0, k), [k, n)
      if(is_null(this)) { return make_pair(nullptr, nullptr); }
      if(k <= lo->size()) {
        auto s = lo->split(k);
        lo = s.second;
        return make_pair(s.first, update());
      } else {
        auto s = hi->split(k - lo->size() - 1);
        hi = s.first;
        return make_pair(update(), s.second);
      }
    }

    int indexOf(T x) {
      if(is_null(this)) { return -1; }
      if(x == this->val) { return lo->size(); }
      if(x <  this->val) {
        return lo->indexOf(x);
      } else {
        return lo->size() + 1 + hi->indexOf(x);
      }
    }

    T valueAt(int pos) {
      if(is_null(this)) { return nullval; }
      int loSize = lo->size();
      if(loSize == pos) { return val; }
      if(loSize > pos) {
        return lo->valueAt(pos);
      } else {
        return hi->valueAt(pos - lo->size() - 1);
      }
    }

    int lowerBound(T x) {
      if(is_null(this)) { return 0; }
      if(x <= this->val) { return lo->lowerBound(x); }
      return hi->lowerBound(x) + lo->size() + 1;
    }

    int upperBound(T x) {
      if(is_null(this)) { return 0; }
      if(x >= this->val) { return lo->size() + 1 + hi->upperBound(x); }
      return lo->upperBound(x);
    }

    int count(T x) {
      return upperBound(x) - lowerBound(x);
    }

    Node* insert(int pos, T x) {
      Node *p = new Node(x);
      auto s = split(pos);
      return merge(merge(s.first, p), s.second);
    }

    Node* insert(T x) {
      return insert(lowerBound(x), x);
    }

    Node* deleteAt(int pos) {
      auto s = split(pos);
      auto t = s.second->split(1);
      t.first = nullptr;
      return merge(s.first, t.second);
    }

    void dump(int x) {
      if(is_null(this)) { return; }
      fprintf(stderr, "%c", "([{"[x%3]);
      lo->dump(x+1);
      fprintf(stderr, "%d", this->val);
      hi->dump(x+1);
      fprintf(stderr, "%c", ")]}"[x%3]);
    }
  }; // }}}
  Node *root;
  RBST() { root = nullptr; }
  int size() { return root->size(); }
  int indexOf(T x) { return root->indexOf(x); }
  T valueAt(int pos) { return root->valueAt(pos); }
  int lowerBound(T val) { return root->lowerBound(val); }
  int upperBound(T val) { return root->upperBound(val); }
  int count(T val) { return root->count(val); }
  void insert(T val) { if(count(val)) { return; } root = root->insert(val); }
  void deleteAt(int pos) { root = root->deleteAt(pos); }
  void deleteValue(T val) { deleteAt(indexOf(val)); }
  void dump() { root->dump(0); fprintf(stderr, "\n"); }
};

template <typename T>
class SegTree {
  size_t n;
  size_t depth;
  vector<T> v;
  void init(size_t m);
  T query(size_t a, size_t b, size_t k, size_t l, size_t r);
  T merge(T l, T r);
 public:
  const T INVALID = 0;
  explicit SegTree(size_t m);
  explicit SegTree(const vector<T> &w);
  void update(size_t k, T x); // 配列 w の k 番目 (0-indexed) を x にする。
  T query(size_t a, size_t b); // [a, b) の範囲で尋ねる。
};

template <typename T>
void SegTree<T>::
init(size_t m) {
  n = 1;
  depth = 1;
  while(n < m) {
    n <<= 1;
    ++depth;
  }
  n = n * 2 - 1;
  v.assign(n, INVALID);
}

template <typename T>
SegTree<T>::SegTree(size_t m) {
  init(m);
}

template <typename T>
SegTree<T>::SegTree(const vector<T> &w) {
  size_t m = w.size();
  init(m);
  for(size_t k=0; k<m; ++k) { update(k, w[k]); }
}

template <typename T>
T SegTree<T>::
merge(T l, T r) {
  return l + r;
}

template <typename T>
void SegTree<T>::
update(size_t k, T x) {
  k += (1U << (depth-1)) - 1;
  v[k] += x;
  while(k > 0) {
    k = (k-1) / 2;
    v[k] = merge(v[k*2+1], v[k*2+2]);
  }
}

template <typename T>
T SegTree<T>::
query(size_t a, size_t b, size_t k, size_t l, size_t r) {
  if(r <= a || b <= l) { return INVALID; }
  if(a <= l && r <= b) { return v[k]; }
  T vl = query(a, b, k*2+1, l, (l+r)/2),
    vr = query(a, b, k*2+2, (l+r)/2, r);
  return merge(vl, vr);
}

// [a, b) の範囲 (a, b は 0-indexed)
template <typename T>
T SegTree<T>::
query(size_t a, size_t b) {
  return query(a, b, 0, 0, (n+1)/2);
}

int main(void) {
  int n; scanf("%d", &n);
  RBST<int> rbst;
  int ptr = 0;
  vector<tuple<int, int, int>> v;
  for(int i=0; i<n; ++i) {
    int a, b, c; scanf("%d%d%d", &a, &b, &c);
    v.emplace_back(a, b, c);
    rbst.insert(b);
    if(a) { rbst.insert(c); }
  }
  SegTree<i64> seg(rbst.size());
  i64 res = 0;
  for(auto tup : v) {
    int a, b, c; tie(a, b, c) = tup;
    if(a == 0) {
      int idx = rbst.indexOf(b);
      seg.update(idx, c);
    } else {
      int idx0 = rbst.indexOf(b),
          idx1 = rbst.indexOf(c);
      res += seg.query(idx0, idx1+1);
    }
  }
  printf("%ld\n", res);
  return 0;
}