結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2019-11-08 12:28:15 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
コンパイルメッセージ
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); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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;}