結果

問題 No.749 クエリ全部盛り
ユーザー 👑 testestesttestestest
提出日時 2018-04-18 19:02:08
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 379 ms / 3,000 ms
コード長 2,991 bytes
コンパイル時間 861 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 83,712 KB
最終ジャッジ日時 2024-06-27 04:31:45
合計ジャッジ時間 4,623 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 64 ms
83,700 KB
testcase_01 AC 61 ms
83,712 KB
testcase_02 AC 62 ms
83,712 KB
testcase_03 AC 60 ms
83,712 KB
testcase_04 AC 60 ms
83,712 KB
testcase_05 AC 63 ms
83,712 KB
testcase_06 AC 61 ms
83,712 KB
testcase_07 AC 61 ms
83,712 KB
testcase_08 AC 62 ms
83,712 KB
testcase_09 AC 62 ms
83,712 KB
testcase_10 AC 77 ms
83,712 KB
testcase_11 AC 77 ms
83,692 KB
testcase_12 AC 75 ms
83,696 KB
testcase_13 AC 78 ms
83,712 KB
testcase_14 AC 78 ms
83,712 KB
testcase_15 AC 378 ms
83,712 KB
testcase_16 AC 378 ms
83,712 KB
testcase_17 AC 377 ms
83,696 KB
testcase_18 AC 379 ms
83,712 KB
testcase_19 AC 374 ms
83,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define M 1000000007

//遅延セグ木ここから

//↓ここを変える
typedef struct sayouso{ll p,q,r;}sayouso;
typedef struct atai{ll a,f;}atai;
//↑ここを変える
typedef struct node{sayouso T;atai x;}node;

node lsegN[1<<21],*lseg;
ll lsegNUM,lsegk;

//↓ここから変える
sayouso id={1,0,0};
atai xx(atai x,atai y){
	atai ret;
	ret.a=(x.a+y.a)%M;
	ret.f=(x.f+y.f)%M;
	return ret;
}
atai Tx(sayouso T,atai x){
	atai ret;
	ret.a=(T.p*x.a+T.q*x.f+T.r)%M;
	ret.f=x.f;
	return ret;
}
sayouso TT(sayouso S,sayouso T){
	sayouso ret;
	ret.p=S.p*T.p%M;
	ret.q=(S.p*T.q+S.q)%M;
	ret.r=(S.p*T.r+S.r)%M;
	return ret;
}
sayouso fT(sayouso T,ll k){
	sayouso ret;
	ret.p=T.p;
	ret.q=T.q;
	ret.r=(T.r<<k)%M;
	return ret;
}
//↑ここまで変える

void lseguse(ll n){
	lsegNUM=n;
	lseg=lsegN+lsegNUM;
	lsegk=0;while(n/=2)lsegk++;
}
void lseginit(){
	for(ll i=lsegNUM-1;i>0;i--)lsegN[i].x=xx(lsegN[2*i].x,lsegN[2*i+1].x);
	rep(i,1,2*lsegNUM)lsegN[i].T=id;
}
void lsegupdatesub(ll l,ll r,sayouso T,ll i,ll cl,ll cr,ll ck){
	//disjointなとき
	if(cr<=l||r<=cl)return;
	//完全に含むとき
	if(l<=cl&&cr<=r){
		lsegN[i].T=TT(T,lsegN[i].T);
		return;
	}
	//どちらでもないとき
	//遅延伝播
	lsegN[2*i  ].T=TT(lsegN[i].T,lsegN[2*i  ].T);
	lsegN[2*i+1].T=TT(lsegN[i].T,lsegN[2*i+1].T);
	//再帰的に更新
	ll cm=(cl+cr)/2;
	lsegupdatesub(l,r,T,2*i  ,cl,cm,ck-1);
	lsegupdatesub(l,r,T,2*i+1,cm,cr,ck-1);
	//自身のnodeを更新
	lsegN[i].x=xx(Tx(fT(lsegN[2*i].T,ck-1),lsegN[2*i].x),Tx(fT(lsegN[2*i+1].T,ck-1),lsegN[2*i+1].x));
	lsegN[i].T=id;
}
void lsegupdate(ll l,ll r,sayouso T){lsegupdatesub(l,r,T,1,0,lsegNUM,lsegk);}
atai lsegcalcsub(ll l,ll r,ll i,ll cl,ll cr,ll ck){
	//完全に含むとき
	if(l<=cl&&cr<=r)return Tx(fT(lsegN[i].T,ck),lsegN[i].x);

	ll cm=(cl+cr)/2;
	//遅延伝播(変更はないので配るだけで良い)
	lsegN[2*i  ].T=TT(lsegN[i].T,lsegN[2*i  ].T);
	lsegN[2*i+1].T=TT(lsegN[i].T,lsegN[2*i+1].T);
	lsegN[i].x=Tx(fT(lsegN[i].T,ck),lsegN[i].x);
	lsegN[i].T=id;

	//左側だけ
	if(r<=cm)return lsegcalcsub(l,r,2*i  ,cl,cm,ck-1);
	//右側だけ
	if(cm<=l)return lsegcalcsub(l,r,2*i+1,cm,cr,ck-1);
	//両方
	return xx(lsegcalcsub(l,r,2*i,cl,cm,ck-1),lsegcalcsub(l,r,2*i+1,cm,cr,ck-1));
}
atai lsegcalc(ll l,ll r){return lsegcalcsub(l,r,1,0,lsegNUM,lsegk);}

//遅延セグ木ここまで

int main(){
	int Q;
	scanf("%*d%d",&Q);
	lseguse(1<<20);
	lseg[1].x.f=1;
	rep(i,2,1000010)lseg[i].x.f=(lseg[i-1].x.f+lseg[i-2].x.f)%M;
	lseginit();
	
	while(Q--){
		int q,l,r,k;
		sayouso T;
		scanf("%d%d%d%d",&q,&l,&r,&k);
		r++;
		if(q==0)printf("%lld\n",lsegcalc(l,r).a*k%M);
		else if(q==1){
			T.p=0,T.q=0,T.r=k;
			lsegupdate(l,r,T);
		}else if(q==2){
			T.p=1,T.q=0,T.r=k;
			lsegupdate(l,r,T);
		}else if(q==3){
			T.p=k,T.q=0,T.r=0;
			lsegupdate(l,r,T);
		}else if(q==4){
			T.p=1,T.q=k,T.r=0;
			lsegupdate(l,r,T);
		}
	}
	return 0;
}
0