結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー m_tsubasa
提出日時 2019-09-30 15:09:44
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 694 ms / 2,000 ms
コード長 2,525 bytes
記録
コンパイル時間 2,085 ms
コンパイル使用メモリ 181,816 KB
実行使用メモリ 65,364 KB
最終ジャッジ日時 2024-11-08 10:22:35
合計ジャッジ時間 9,637 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

// 1-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T &, T &)> F;
  int n;
  F f;
  T unit;
  function<long long(T &, long long)> g;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t,
              function<long long(T &, long long)> g)
      : f(f), unit(t), g(g) {
    init(newn);
  }
  void init(int newn) {
    n = 1;
    while(n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }
  void build(vector<T> &v) {
    for(int i = 0; i < v.size(); ++i) dat[i + n] = v[i];
    for(int i = n - 1; i > 0; --i)
      dat[i] = f(dat[(i << 1)], dat[(i << 1) | 1]);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while(k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  long long query(int a, int b, long long x) {
    long long ans = 0;
    for(int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) ans += g(dat[l++], x);
      if(r & 1) ans += g(dat[--r], x);
    }
    return ans;
  }
};

long long n, q;
struct data {
  vector<long long> v, sum;
};
data dummy;
vector<data> v;

int main() {
  auto f = [](data &l, data &r) {
    data newd;
    int lid = 0, rid = 0, lsize = l.v.size(),
        rsize = r.v.size();
    // merge sort
    while(lid < lsize || rid < rsize) {
      if(lid < lsize && rid < rsize) {
        if(l.v[lid] < r.v[rid])
          newd.v.push_back(l.v[lid++]);
        else
          newd.v.push_back(r.v[rid++]);
      }
      else if(lid < lsize)
        newd.v.push_back(l.v[lid++]);
      else
        newd.v.push_back(r.v[rid++]);
    }
    newd.sum.assign(newd.v.size() + 1, 0);
    for(int i = 0; i < newd.v.size(); ++i)
      newd.sum[i + 1] = newd.sum[i] + newd.v[i];
    return newd;
  };
  auto g = [](data &d, long long x) {
    long long ans = *(d.sum.end() - 1);
    int id = upper_bound(d.v.begin(), d.v.end(), x) -
             d.v.begin();
    ans -= d.sum[id];
    return ans - x * ((int)d.v.size() - id);
  };
  dummy.sum.push_back(0);
  cin >> n >> q;
  SegmentTree<data> seg(n, f, dummy, g);
  for(int i = 0; i < n; ++i) {
    data now;
    long long a;
    cin >> a;
    now.v.push_back(a);
    now.sum.push_back(0);
    now.sum.push_back(a);
    v.push_back(now);
  }
  seg.build(v);
  for(int i = 0; i < q; ++i) {
    long long c, l, r, x;
    cin >> c >> l >> r >> x;
    cout << seg.query(l - 1, r, x) << endl;
  }
  return 0;
}
0