結果

問題 No.749 クエリ全部盛り
ユーザー matsukin11111matsukin11111
提出日時 2019-11-08 12:28:15
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 901 ms / 3,000 ms
コード長 4,023 bytes
コンパイル時間 884 ms
コンパイル使用メモリ 86,132 KB
実行使用メモリ 85,632 KB
最終ジャッジ日時 2024-09-15 00:49:51
合計ジャッジ時間 8,364 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 104 ms
85,480 KB
testcase_01 AC 106 ms
85,376 KB
testcase_02 AC 106 ms
85,476 KB
testcase_03 AC 105 ms
85,504 KB
testcase_04 AC 105 ms
85,504 KB
testcase_05 AC 115 ms
85,632 KB
testcase_06 AC 113 ms
85,376 KB
testcase_07 AC 115 ms
85,376 KB
testcase_08 AC 114 ms
85,504 KB
testcase_09 AC 114 ms
85,376 KB
testcase_10 AC 158 ms
85,504 KB
testcase_11 AC 155 ms
85,504 KB
testcase_12 AC 157 ms
85,504 KB
testcase_13 AC 158 ms
85,504 KB
testcase_14 AC 156 ms
85,504 KB
testcase_15 AC 879 ms
85,504 KB
testcase_16 AC 894 ms
85,504 KB
testcase_17 AC 901 ms
85,376 KB
testcase_18 AC 895 ms
85,504 KB
testcase_19 AC 900 ms
85,504 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:139:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  139 |         scanf("%*d%d",&Q);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:148:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |                 scanf("%d%d%d%d",&q,&l,&r,&k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


ll M = 1e9 + 7;
ll MOD = M;


//遅延セグ木ここから

//↓ここを変える
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() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	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