結果

問題 No.749 クエリ全部盛り
ユーザー chocoruskchocorusk
提出日時 2019-09-06 16:06:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 650 ms / 3,000 ms
コード長 4,385 bytes
コンパイル時間 1,249 ms
コンパイル使用メモリ 123,740 KB
実行使用メモリ 43,932 KB
最終ジャッジ日時 2023-09-06 05:01:16
合計ジャッジ時間 6,813 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
11,444 KB
testcase_01 AC 5 ms
11,384 KB
testcase_02 AC 6 ms
11,392 KB
testcase_03 AC 5 ms
11,376 KB
testcase_04 AC 5 ms
11,588 KB
testcase_05 AC 7 ms
11,420 KB
testcase_06 AC 8 ms
11,460 KB
testcase_07 AC 7 ms
11,336 KB
testcase_08 AC 7 ms
11,348 KB
testcase_09 AC 7 ms
11,660 KB
testcase_10 AC 31 ms
11,512 KB
testcase_11 AC 31 ms
11,372 KB
testcase_12 AC 31 ms
11,372 KB
testcase_13 AC 31 ms
11,660 KB
testcase_14 AC 31 ms
11,512 KB
testcase_15 AC 626 ms
43,932 KB
testcase_16 AC 624 ms
43,796 KB
testcase_17 AC 634 ms
43,700 KB
testcase_18 AC 639 ms
43,812 KB
testcase_19 AC 650 ms
43,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
template<int MOD>
struct ModInt{
	int x;
	ModInt(): x(0){}
	ModInt(ll y): x(y>=0 ? y%MOD : (MOD-(-y)%MOD)%MOD){}

	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=MOD-p.x)>=MOD) x-=MOD;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1ll*x*p.x%MOD);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inv();
		return *this;
	}

	ModInt operator-() const{ return ModInt(-x);}
	ModInt operator+(const ModInt &p) const{ return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p) const{ return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p) const{ return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p) const{ return ModInt(*this)/=p;}
	bool operator==(const ModInt &p) const{ return x==p.x;}
	bool operator!=(const ModInt &p) const{ return x!=p.x;}

	ModInt pow(ll n) const{
		ModInt ret(1), p(x);
		while(n){
			if(n&1) ret*=p;
			p*=p;
			n>>=1;
		}
		return ret;
	}
	ModInt inv() const{
		return pow(MOD-2);
	}
};
const int MOD=1e9+7;
using modint=ModInt<MOD>;
typedef pair<modint, modint> P;
typedef pair<P, modint> Pm;
modint fib[1000010], fibs[1000010];

template<typename Monoid, typename OperatorMonoid=Monoid>
struct LazySegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	using G=function<Monoid(Monoid, OperatorMonoid, int, int)>;
	using H=function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
	int sz;
	vector<Monoid> data;
	vector<OperatorMonoid> lazy;
	const F f;
	const G g;
	const H h;
	const Monoid e1;
	const OperatorMonoid e0;

	LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){
		sz=1;
		while(sz<n) sz<<=1;
		data.resize(2*sz-1, e1);
		lazy.resize(2*sz-1, e0);
	}

	void build(vector<Monoid> v){
		for(int i=0; i<v.size(); i++) data[i+sz-1]=v[i];
		for(int i=sz-2; i>=0; i--) data[i]=f(data[2*i+1], data[2*i+2]);
	}

	void eval(int k, int l, int r){
		if(lazy[k]!=e0){
			data[k]=g(data[k], lazy[k], l, r);
			if(k<sz-1){
				lazy[2*k+1]=h(lazy[2*k+1], lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2], lazy[k]);
			}
		}
		lazy[k]=e0;
	}

	void update(int a, int b, const OperatorMonoid &x, int k, int l, int r){
		eval(k, l, r);
		if(r<=a || b<=l) return;
		if(a<=l && r<=b){
			lazy[k]=h(lazy[k], x);
			eval(k, l, r);
		}else{
			update(a, b, x, 2*k+1, l, (l+r)/2);
			update(a, b, x, 2*k+2, (l+r)/2, r);
			data[k]=f(data[2*k+1], data[2*k+2]);
		}
	}
	void update(int a, int b, const OperatorMonoid &x){
		return update(a, b, x, 0, 0, sz);
	}

	Monoid find(int a, int b, int k, int l, int r){
		eval(k, l, r);
		if(b<=l || r<=a) return e1;
		if(a<=l && r<=b) return data[k];
		else return f(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r));
	}
	Monoid find(int a, int b){
		return find(a, b, 0, 0, sz);
	}
	Monoid operator[](const int &k){
		return find(k, k+1);
	}
};
int main()
{
	int n, q;
	scanf("%d %d", &n, &q);
	fib[0]=0, fib[1]=1;
	for(int i=2; i<n; i++) fib[i]=fib[i-1]+fib[i-2];
	fibs[0]=fibs[1]=0;
	for(int i=1; i<n; i++) fibs[i+1]=fibs[i]+fib[i];
	auto f=[](modint a, modint b){ return a+b;};
	auto g=[&](modint a, Pm p, int l, int r){
		modint x=p.first.first, y=p.first.second, z=p.second;
		return x*a+y*(r-l)+z*(fibs[r]-fibs[l]);
	};
	auto h=[](Pm p1, Pm p2){
		modint x1=p1.first.first, y1=p1.first.second, z1=p1.second;
		modint x2=p2.first.first, y2=p2.first.second, z2=p2.second;
		return Pm(P(x1*x2, x2*y1+y2), x2*z1+z2);
	};
	LazySegmentTree<modint, Pm> seg(n, f, g, h, 0, Pm(P(1, 0), 0));
	for(int z=0; z<q; z++){
		int p, l, r, k;
		scanf("%d %d %d %d", &p, &l, &r, &k);
		if(p==0) printf("%d\n", (modint(k)*seg.find(l, r+1)).x);
		else if(p==1) seg.update(l, r+1, Pm(P(0, k), 0));
		else if(p==2) seg.update(l, r+1, Pm(P(1, k), 0));
		else if(p==3) seg.update(l, r+1, Pm(P(k, 0), 0));
		else seg.update(l, r+1, Pm(P(1, 0), k));
	}
	return 0;
}
0