結果

問題 No.877 Range ReLU Query
ユーザー _____TAB_____
提出日時 2020-04-19 03:05:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 861 ms / 2,000 ms
コード長 2,094 bytes
コンパイル時間 1,952 ms
コンパイル使用メモリ 105,196 KB
最終ジャッジ日時 2025-01-09 21:22:29
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename T>
struct SegmentTree{
private:
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
public:
  SegmentTree(){};
  SegmentTree(F f,T ti) : f(f),ti(ti) {}
  void build(int n_){
    n = n_;
    dat.assign(2*n,ti);
  }
  void build(const vector<T> &v){
    int n_ = v.size();
    build(n_);
    for(int i = 0; i < n; ++i) dat[n+i]=v[i];
    for(int i = n-1; i >= 0; --i)
      dat[i]=f(dat[2*i+0],dat[2*i+1]);
  }
  long long query(int a,int b, long long x){
    long long ret = 0;
    for(int l = a+n, r = b+n; l < r; l >>= 1, r >>= 1){
      if(l&1) ret += dat[l++].query(x);
      if(r&1) ret += dat[--r].query(x);
    }
    return ret;
  }
};

struct value {
  vector<long long> dat;
  vector<long long> sum;
  value(){}
  value(long long x) : dat(1,x), sum(1,x) {}
  void merge(const value& rhs){
    size_t sz = dat.size();
    dat.insert(dat.end(),rhs.dat.begin(),rhs.dat.end());
    sum.insert(sum.end(),rhs.sum.begin(),rhs.sum.end());
    if(!sz) return;
    inplace_merge(dat.begin(),dat.begin()+sz,dat.end());
    sum[0] = dat[0];
    for(size_t i = 1; i < sum.size(); ++i)
      sum[i] = sum[i-1] + dat[i];
  }
  long long query(long long x){
    long long idx = upper_bound(dat.begin(), dat.end(), x) - dat.begin();
    long long sz = sum.size();
    if(idx == sz) return 0LL;
    long long ret = sum.back();
    if(idx > 0) ret -= sum[idx-1];
    ret -= (sz-idx)*x;
    return ret;
  }
};

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

  vector<value> A;
  for(int i = 0; i < N; ++i){
    int a;
    cin >> a;
    A.emplace_back(a);
  }

  function<value(value,value)> f = [](value a, value b){
                                     a.merge(b);
                                     return a;
                                   };

  SegmentTree<value> st(f,value());
  st.build(A);
  
  while(Q--){
    long long t, l, r, x;
    cin >> t >> l >> r >> x;
    --l;
    if(t == 1){
      cout << st.query(l,r,x) << endl;
    }
  }
}
0