結果

問題 No.879 Range Mod 2 Query
ユーザー okuraofvegetabl
提出日時 2020-02-12 00:42:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,887 bytes
コンパイル時間 2,261 ms
コンパイル使用メモリ 184,240 KB
実行使用メモリ 21,864 KB
最終ジャッジ日時 2024-10-01 13:36:47
合計ジャッジ時間 7,993 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000 //2e9
#define LLINF 1000000000000000000ll // 1e18
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define dmp(x) cerr << #x << ": " << x << endl;

template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}

template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T,vector<T>,greater<T>>;
template<class T> vector<T> vect(int len,T elem){ return vector<T>(len,elem); }

template<class T,class U>
ostream& operator << (ostream& os,const pair<T,U>& p){
  os << p.fi << ',' << p.sec; return os;
}
template<class T,class U>
istream& operator >> (istream& is,pair<T,U>& p){
  is >> p.fi >> p.sec; return is;
}
template<class T>
ostream& operator << (ostream &os,const vector<T> &vec){
  for(int i=0;i<vec.size();i++){
    os << vec[i];
    if(i+1<vec.size())os << ' ';
  }
  return os;
}
template<class T>
istream& operator >> (istream &is,vector<T>& vec){
  for(int i=0;i<vec.size();i++)is >> vec[i];
  return is;
}
void fastio(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(20);
}

// verified https://judge.yosupo.jp/submission/3622

template<class D>
struct SegmentTreeBeats{
  using DMerger = function<D(D,D)>;
  vector<D> seg;
  int length;
  DMerger dm;
  D d_unit;
  SegmentTreeBeats(const vector<D>& vec,DMerger dm,D d_unit = D()):length(1),dm(dm){
    while(length<vec.size())length <<= 1;
    seg.assign(length*2,d_unit);
    for(int i=0;i<vec.size();i++){
      seg[i+length-1] = vec[i];
    }
    for(int i=length-2;i>=0;i--){
      seg[i] = dm(seg[i*2+1],seg[i*2+2]);
    }
  }
  template<class F,class... Args>
  void update(int a,int b,int k,int l,int r,F break_or_puttag,Args... args){
    if(r<=a||b<=l)return;
    if(a<=l&&r<=b&&(seg[k].*break_or_puttag)(args...))return;
    seg[k].pushdown(seg[k*2+1],seg[k*2+2]);
    update(a,b,k*2+1,l,(l+r)/2,break_or_puttag,args...);
    update(a,b,k*2+2,(l+r)/2,r,break_or_puttag,args...);
    seg[k] = dm(seg[k*2+1],seg[k*2+2]);
  }
  template<class F,class... Args>
  void update(int a,int b,F break_or_puttag,Args... args){
    update(a,b,0,0,length,break_or_puttag,args...);
  }
  template<class Getter,class QMerger,class Q>
  Q query(int a,int b,int k,int l,int r,Getter getter,QMerger qm,Q q_unit){
    if(r<=a||b<=l)return q_unit;
    if(a<=l&&r<=b)return (seg[k].*getter)();
    seg[k].pushdown(seg[k*2+1],seg[k*2+2]);
    Q lch = query(a,b,k*2+1,l,(l+r)/2,getter,qm,q_unit);
    Q rch = query(a,b,k*2+2,(l+r)/2,r,getter,qm,q_unit);
    return qm(lch,rch);
  }
  template<class Getter,class QMerger,class Q>
  Q query(int a,int b,Getter getter,QMerger qm,Q q_unit){
    return query(a,b,0,0,length,getter,qm,q_unit);
  }
};

// requirements :
// 
// static Data merge(Data l,Data r)
//
// void pushdown(Data& l,Data& r) (push down tag)
// 
// for each update query :
// bool break_or_puttag_[QUERY] (TAGTYPE tag)
//   if puttag condition is satisfied, update data and put tag
//   return : if break condition or puttag condition is satisfied, return true, otherwise return false

struct Data{
  ll tag,num,sum,mx,mi;
  Data(ll v = 0ll):tag(0ll),num(1ll),sum(v),mx(v),mi(v){}
  static Data merge(Data l,Data r){
    Data ret;
    ret.tag = 0ll;
    ret.num = l.num + r.num;
    ret.sum = l.sum + r.sum;
    ret.mx = max(l.mx,r.mx);
    ret.mi = min(l.mi,r.mi);
    return ret;
  }
  bool add(ll x){
    sum += num*x;
    mx += x;
    mi += x;
    tag += x;
    return true;
  }
  bool mod(ll x){
    if(mx<x)return true;
    if(mi==mx){
      ll rem = mx%x;
      add(rem-mx);
      return true;
    }
    return false;
  }
  void pushdown(Data& l,Data& r){
    l.add(tag);
    r.add(tag);
    tag = 0ll;
  }
  ll get_sum(){ return sum; }
  ll get_min(){ return mi; }
  ll get_max(){ return mx; }
};


void yukicoder879(){
  int N,Q;
  cin >> N >> Q;
  vector<Data> vec;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    vec.emplace_back(a);
  }
  SegmentTreeBeats<Data> seg(vec,Data::merge);
  for(int i=0;i<Q;i++){
    int type,l,r;
    ll x;
    cin >> type;
    if(type==1){
      cin >> l >> r; l--;
      seg.update(l,r,&Data::mod,2);
    }
    if(type==2){
      cin >> l >> r >> x; l--;
      seg.update(l,r,&Data::add,x);
    }
    if(type==3){
      cin >> l >> r; l--;
      cout << seg.query(l,r,&Data::get_sum,[](ll x,ll y){return x+y;},0ll) << endl;
    }
  }
}



signed main(){
  fastio();
  // yosupo_RangeChminChmaxAddRangeSum();
  // AOJ_DSL_2_F();
  // AOJ_DSL_2_G();
  // AOJ_DSL_2_I();
  // AOJ_DSL_2_H();
  // HDU5306_GorgeousSequnence();
  yukicoder879();
  return 0;
}
0