結果
問題 | No.749 クエリ全部盛り |
ユーザー | matsukin11111 |
提出日時 | 2019-11-08 12:21:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,134 bytes |
コンパイル時間 | 1,369 ms |
コンパイル使用メモリ | 86,436 KB |
実行使用メモリ | 85,376 KB |
最終ジャッジ日時 | 2024-09-15 00:49:20 |
合計ジャッジ時間 | 5,275 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | RE | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
ソースコード
#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;cin >> Q;lseguse(1 << 20);lsegN[1].x.f = 1;for (int i = 2; i < 1000100; i++)lsegN[i].x.f = (lsegN[i - 1].x.f + lsegN[i-2].x.f) % MOD;lseginit();for (int i = 0; i < Q; i++) {ll q, l, r, k;sayouso T;cin >> q >> l >> r >> k;if (q == 0)puts(lsegcalc(l, r + 1).a*k%MOD);else if (q == 1) {T.p = 0; T.q = 0; T.r = k;lsegupdate(l,r+1,T);}else if (q == 2) {T.p = 1; T.q = 0; T.r = k;lsegupdate(l, r + 1, T);}else if (q == 3) {T.p = k; T.q = 0; T.r = 0;lsegupdate(l, r + 1, T);}else if (q == 4) {T.p = 1; T.q = k; T.r = 0;lsegupdate(l, r + 1, T);}}return 0;}