結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー cureskol
提出日時 2019-10-31 12:44:25
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 637 ms / 2,000 ms
コード長 4,143 bytes
記録
コンパイル時間 2,232 ms
コンパイル使用メモリ 180,792 KB
実行使用メモリ 70,904 KB
最終ジャッジ日時 2024-11-08 10:23:11
合計ジャッジ時間 8,568 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

typedef pair<vector<int>,vector<int>> T;
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;  //セグ木の幅
  F f;  //モノイドの作用
  T ti;  //初期値
  vector<T> dat;  //セグ木で使う配列 一番上に使われるのがdat[1] 一番下の段の左端がdat[n]
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}  //fがモノイドとしての作用、tiが単位元

  void init(int n_){  //ただの初期化
    n=1;
    while(n<n_) n<<=1;  //nが実際にとる２べきの幅
    dat.assign(n<<1,ti);  //dat配列は幅の２倍あってその全てにtiを代入
  }

  void build(const vector<T> &v){  //vector vに合わせた初期化
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];  //v[i]を一番子の所に代入
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);  //iの子供は2*i、2*i+1
  }

  void set_val(int k,T x){  //（0-indexedで）kにxを代入
    dat[k+=n]=x;
    while(k>>=1)  //kがどんどん自分の親になっていく、0になったらおしまい
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }

  int A(T &v,int x){//vに対してのそれなので、xより大きいやつからx引いて和を出す
    vector<int> &retsu=v.first,&wa=v.second;
    int N=retsu.size();
    if(retsu.size()==0)return 0;
    if(retsu[0]>=x)return (wa[N]-x*N);
    if(retsu[N-1]<=x)return 0;
    int l=0,r=N;
    while(r-l>1){
      int m=(r+l)>>1;
      if(retsu[m]>x)r=m;
      else l=m;
    }
    return (wa[N]-wa[r])-x*(N-r);
  }

  int query(int a,int b,int x){  //[a,b)の範囲のモノイドの作用を返す
    int vl=0,vr=0;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl+=A(dat[l++],x);  //左端を使いたくなるのはブロックが奇数の時
      if(r&1) vr+=A(dat[--r],x);  //右端〃偶数の時（開区間なのでr:奇数で反応）
    }
    return vl+vr;
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){  //dat[k]:[l,r)の間にいるenを返す
    //下のfind用なので先にそっち読むべき
    //accはst~lとかで確定している値
    if(l+1==r){  //答えがちゃんと存在するならこのlが答え
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1; //入るならk-n(==l)を、入らないなら-1を返す
    }
    int m=(l+r)>>1;  //にぶたんのそれ
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);  //mがstより後ろなら明らかにl=m;
    if(st<=l&&!check(f(acc,dat[k]))){  //今見てるk全部でもダメ(mだと足りないのでl=mにする）
      acc=f(acc,dat[k]);  //kは全部accに加えた上で-1を返す
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);  //まず[l,m)の中にenがいるか探す
    if(~vl) return vl;  //いたならそれを返す(if(~vl)は-1以外にのみ反応する)
    return find(st,check,acc,(k<<1)|1,m,r);  //いなかったら[m,r)の中にenがいるのでそれを返す
    //acc=f(acc,dat[k]);がここで効いてる
  }

  template<typename C>
  int find(int st,C &check){
    //check(f(dat[st]~dat[en-1]))=false,check(f(dat[st]~dat[en]))＝trueとなるenを返す
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

signed main(){
  int n,q;cin>>n>>q;
  vector<T> v(n);
  vector<int> ans;
  for(int i=0;i<n;i++){
    int a;cin>>a;
    v[i].first.push_back(a);
    v[i].second.push_back(0);
    v[i].second.push_back(a);
  }
  auto f=[](T atomato,T btomato){
    vector<int> retsu,wa;
    auto a=atomato.first,b=btomato.first;
    wa.push_back(0);
    int newest=0,tmp;
    int ax=0,bx=0;
    while(ax<a.size()||bx<b.size()){
      if(ax==a.size())tmp=b[bx++];
      else if(bx==b.size())tmp=a[ax++];
      else if(a[ax]<b[bx])tmp=a[ax++];
      else tmp=b[bx++];
      retsu.push_back(tmp);
      wa.push_back(newest=newest+tmp);
    }
    return T(retsu,wa);
  };
  SegmentTree seg(f,T(vector<int>(),vector<int>()));
  seg.build(v);
  while(q--){
    int c,a,b,x;cin>>c>>a>>b>>x;
    ans.push_back(seg.query(--a,b,x));
  }
  for(int p:ans)cout<<p<<endl;
}
0