結果

問題 No.877 Range ReLU Query
ユーザー Haar
提出日時 2020-05-07 06:11:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,007 ms / 2,000 ms
コード長 3,967 bytes
コンパイル時間 3,574 ms
コンパイル使用メモリ 217,608 KB
最終ジャッジ日時 2025-01-10 07:25:40
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...)
#endif


template <typename Monoid>
class PersistentSegmentTree{
  using value_type = typename Monoid::value_type;
  
  struct node{
    value_type value;
    node *left = nullptr, *right = nullptr;
    node(const value_type &value): value(value){}
  };

  int depth;
  node *root = nullptr;

  PersistentSegmentTree(int depth, node *root): depth(depth), root(root){}
  
  node* init(node *t, const std::vector<value_type> &init_list, int d, int &pos){
    if(d == depth){
      t = new node(pos < (int)init_list.size() ? init_list[pos] : Monoid::id());
      ++pos;
    }else{
      t = new node(Monoid::id());
      t->left = init(t->left, init_list, d+1, pos);
      t->right = init(t->right, init_list, d+1, pos);
      t->value = Monoid::op(t->left->value, t->right->value);
    }
    return t;
  }
  
public:
  PersistentSegmentTree(const std::vector<value_type> &init_list){
    const int size = init_list.size();
    depth = size == 1 ? 1 : 32 - __builtin_clz(size-1) + 1;
    int pos = 0;
    root = init(root, init_list, 1, pos);
  }
  
  PersistentSegmentTree(int size){
    depth = size == 1 ? 1 : 32 - __builtin_clz(size-1) + 1;
    int pos = 0;
    root = init(root, std::vector<value_type>(size, Monoid::id()), 1, pos);
  }
  
protected:
  node* update(node *t, int l, int r, int pos, const value_type &val) const {
    if(r <= pos or pos + 1 <= l){
      return t;
    }else if(pos <= l and r <= pos + 1){
      return new node(val);
    }else{
      const int m = (l + r) >> 1;
      auto lp = update(t->left, l, m, pos, val);
      auto rp = update(t->right, m, r, pos, val);

      node *s = new node(Monoid::op(lp->value, rp->value));

      s->left = lp;
      s->right = rp;
      
      return s;
    }
  }

public:
  PersistentSegmentTree update(int i, const value_type &val) const {
    node *t = update(root, 0, 1 << (depth-1), i, val);
    return PersistentSegmentTree(depth, t);
  }

protected:
  value_type get(node *t, int i, int j, int l, int r) const {
    if(i <= l and r <= j) return t->value;
    if(r <= i or j <= l) return Monoid::id();
    const int m = (l + r) >> 1;
    return Monoid::op(get(t->left, i, j, l, m), get(t->right, i, j, m, r));
  }

public:
  value_type get(int i, int j) const {
    return get(root, i, j, 0, 1 << (depth-1));
  }

  value_type at(int i) const {
    return get(i, i+1);
  }
};


template <typename T>
struct SumMonoid{
  using value_type = T;
  constexpr inline static value_type id(){return 0;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;}
};


template <typename M1, typename M2>
struct PairMonoid{
  using value_type = std::pair<typename M1::value_type, typename M2::value_type>;

  constexpr inline static value_type id(){
    return {M1::id(), M2::id()};
  }

  constexpr inline static value_type op(const value_type &a, const value_type &b){
    return {M1::op(a.first, b.first), M2::op(a.second, b.second)};
  }
};


using M = SumMonoid<int64_t>;
using Seg = PersistentSegmentTree<PairMonoid<M, M>>;

int main(){
  int N, Q; std::cin >> N >> Q;

  std::vector<int64_t> a(N);
  for(int i = 0; i < N; ++i) std::cin >> a[i];

  std::vector<int64_t> l(Q), r(Q), x(Q);
  for(int i = 0; i < Q; ++i){
    int type;
    std::cin >> type >> l[i] >> r[i] >> x[i];
  }

  std::vector<Seg> seg;
  seg.push_back(Seg(N));

  {
    std::vector<std::pair<int64_t, int>> b(N);
    for(int i = 0; i < N; ++i) b[i] = std::make_pair(a[i], i);
    std::sort(b.rbegin(), b.rend());

    for(auto [v, i] : b){
      auto &s = seg.back();
      seg.push_back(s.update(i, std::make_pair(v, 1)));
    }
  }

  std::sort(a.rbegin(), a.rend());

  for(int i = 0; i < Q; ++i){
    int j = a.rend() - std::lower_bound(a.rbegin(), a.rend(), x[i]);

    auto [v, c] = seg[j].get(l[i]-1, r[i]);
    auto ans = v - x[i] * c;

    std::cout << ans << "\n";
  }

  return 0;
}
0