#292898 (C++17) No.749 クエリ全部盛り

提出ソース

結果

問題	No.749 クエリ全部盛り
ユーザー	beet
提出日時	2018-10-19 22:06:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	670 ms / 3,000 ms
コード長	4,463 bytes
コンパイル時間	2,846 ms
コンパイル使用メモリ	231,364 KB
実行使用メモリ	97,792 KB
最終ジャッジ日時	2024-11-18 20:47:17
合計ジャッジ時間	7,627 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	4 ms 5,248 KB
testcase_06	AC	4 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	29 ms 5,248 KB
testcase_11	AC	29 ms 5,248 KB
testcase_12	AC	29 ms 5,248 KB
testcase_13	AC	29 ms 5,248 KB
testcase_14	AC	30 ms 5,248 KB
testcase_15	AC	670 ms 97,664 KB
testcase_16	AC	669 ms 97,664 KB
testcase_17	AC	657 ms 97,664 KB
testcase_18	AC	649 ms 97,664 KB
testcase_19	AC	646 ms 97,792 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(int n_,F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){init(n_);}
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(int k){
    return g(dat[k],laz[k]);
  }
  inline void eval(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void recalc(int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};


template<typename T,T MOD = 1000000007>
struct Mint{
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(int k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
  
  Mint inv(){return pow(MOD-2);}
  
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
  
  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-(){return v?MOD-v:v;}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

};

//INSERT ABOVE HERE
signed main(){
  int n,q;
  scanf("%d %d",&n,&q);
  vector<int> t(q),l(q),r(q),k(q);
  for(int i=0;i<q;i++)
    scanf("%d %d %d %d",&t[i],&l[i],&r[i],&k[i]);

  using M = Mint<int>;

  using T = tuple<M, M, M>;
  using E = tuple<bool, M, M, M, M>;

  auto f=[](T a,T b){
	   M as,ac,af;
	   M bs,bc,bf;
	   tie(as,ac,af)=a;
	   tie(bs,bc,bf)=b;
	   return T(as+bs,ac+bc,af+bf);
	 };

  auto g=[](T a,E b){
	   M as,ac,af;
	   M bu,ba,bm,bf;
	   bool upd;
	   tie(as,ac,af)=a;
	   tie(upd,bu,ba,bm,bf)=b;
	   if(upd) as=bu*ac;
	   as*=bm;
	   as+=ba*ac;
	   as+=bf*af;
	   return T(as,ac,af);
	 };

  auto h=[](E a,E b){
	   M au,aa,am,af;
	   M bu,ba,bm,bf;
	   bool ua,ub;
	   tie(ua,au,aa,am,af)=a;
	   tie(ub,bu,ba,bm,bf)=b;
	   if(ub) return b;
	   aa*=bm;	   
	   am*=bm;
	   af*=bm;
	   
	   aa+=ba;
	   af+=bf;
	   return E(ua,au,aa,am,af);
	 };

  T ti(M(0),M(0),M(0));
  E ei(false,M(0),M(0),M(1),M(0));
  SegmentTree<T, E> seg(n,f,g,h,ti,ei);

  vector<M> fib(n);
  vector<T> vt(n);
  for(int i=0;i<n;i++){
    if(i==0) fib[i]=M(0);
    if(i==1) fib[i]=M(1);
    if(i>=2) fib[i]=fib[i-1]+fib[i-2];
    vt[i]=T(M(0),M(1),fib[i]);
  }
  seg.build(n,vt);
  
  for(int i=0;i<q;i++){
    r[i]++;
    M v(k[i]);
    if(t[i]==0){
      T res=seg.query(l[i],r[i]);
      printf("%d\n",(v*get<0>(res)).v);
    }
    if(t[i]==1){
      E x(true,v,M(0),M(1),M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==2){
      E x(false,M(0),v,M(1),M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==3){
      E x(false,M(0),M(0),v,M(0));
      seg.update(l[i],r[i],x);
    }
    if(t[i]==4){
      E x(false,M(0),M(0),M(1),v);
      seg.update(l[i],r[i],x);
    }
  }
  
  return 0;
}

yukicoder

結果

テストケース

ソースコード