結果

問題 No.749 クエリ全部盛り
コンテスト
ユーザー Nachia
提出日時 2020-10-07 23:10:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 731 ms / 3,000 ms
コード長 2,145 bytes
コンパイル時間 1,822 ms
コンパイル使用メモリ 175,748 KB
実行使用メモリ 172,600 KB
最終ジャッジ日時 2024-07-20 04:19:24
合計ジャッジ時間 6,649 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

const ULL M=1000000007;
ULL FS[1000001];

struct S{ ULL x,i,z; };
S op(S l,S r){ return {(l.x+r.x)%M,min(l.i,r.i),(l.z+r.z)%M }; }
S e(){ return {0,~0ull,0}; }
struct F{ ULL upd,mul,fib,add; };
S ef(F f,S a){
	if(~f.upd) a.x = f.upd*a.z%M;
	a.x = (a.x*f.mul)%M;
	a.x = (a.x+f.fib*(FS[a.i+a.z]+M-FS[a.i]))%M;
	a.x = (a.x+f.add*a.z)%M;
	return a;
}
F ur(F f,F g){
	if(~f.upd) g = { f.upd,1,0,0 };
	g.mul = (g.mul*f.mul)%M;
	g.add = (g.add*f.mul+f.add)%M;
	g.fib = (g.fib*f.mul+f.fib)%M;
	return g;
}
F id(){ return {~0ull,1,0,0}; }

struct RQ{
	struct Node{ S v; F r; };
	int N;
	vector<Node> V;

	void spread(int i){
		V[i].v = ef(V[i].r,V[i].v);
		if(i<N){
			V[i*2].r = ur(V[i].r,V[i*2].r);
			V[i*2+1].r = ur(V[i].r,V[i*2+1].r);
		}
		V[i].r=id();
	}
	RQ(vector<S> A){
		N=1; while(N<A.size()) N*=2;
		V.assign(N*2,{e(),id()});
		rep(i,A.size()) V[N+i].v = A[i];
		for(int i=N-1; i>=1; i--)
			V[i].v = op(V[i*2].v, V[i*2+1].v);
	}

	void apply(int l,int r, F v,int a=0,int b=0,int i=-1){
		if(i==-1){ a=0; b=N; i=1; }
		if(r<=a || b<=l){ spread(i); return; }
		else if(l<=a && b<=r){ V[i].r = ur(v,V[i].r); spread(i); return; }
		spread(i);
		apply(l,r,v,a,(a+b)/2,i*2);
		apply(l,r,v,(a+b)/2,b,i*2+1);
		V[i].v = op(V[i*2].v,V[i*2+1].v);
	}

	S prod(int l,int r,int a=0,int b=0,int i = -1){
		if(i==-1){ a=0; b=N; i=1; }
		if(r<=a || b<=l) return e();
		spread(i);
		if(l<=a && b<=r) return V[i].v;
		S q1 = prod(l,r,a,(a+b)/2,i*2);
		S q2 = prod(l,r,(a+b)/2,b,i*2+1);
		q1 = op(q1,q2);
		return q1;
	}
};

int main(){
	int N,Q; cin>>N>>Q;
	FS[0]=0; FS[1]=0; FS[2]=1;
	for(int i=3; i<=N; i++) FS[i]=(FS[i-1]+FS[i-2])%M;
	rep(i,N) FS[i+1]=(FS[i]+FS[i+1])%M;

	vector<S> rqinit(N);
	rep(i,N) rqinit[i] = {0,ULL(i),1};
	RQ G(rqinit);

	while (Q--){
		ULL q, l,r, k; cin>>q>>l>>r>>k; r++;
		if(q==0){ cout<<(G.prod(l,r).x*k%M)<<endl; }
		if(q==1){ G.apply(l,r,{ k,1,0,0 }); }
		if(q==2){ G.apply(l,r,{ ~0ull,1,0,k }); }
		if(q==3){ G.apply(l,r,{ ~0ull,k,0,0 }); }
		if(q==4){ G.apply(l,r,{ ~0ull,1,k,0 }); }
	}

	return 0;
}
0