結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2018-10-19 23:19:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 849 ms / 3,000 ms |
コード長 | 2,804 bytes |
コンパイル時間 | 757 ms |
コンパイル使用メモリ | 92,468 KB |
実行使用メモリ | 100,044 KB |
最終ジャッジ日時 | 2024-11-18 22:32:15 |
合計ジャッジ時間 | 6,141 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <unordered_map>#include <unordered_set>#include <random>using namespace std;typedef long long int ll;typedef pair<ll, int> P;const int MAX_N=1<<20;const ll MOD=1e9+7;ll sum[2*MAX_N-1], parta[2*MAX_N-1], partb[2*MAX_N-1], part[2*MAX_N-1], partf[2*MAX_N-1];int m;ll fib1[MAX_N], fib[MAX_N];void init(int n){m=1;while(m<n) m*=2;for(int i=0; i<2*m-1; i++){parta[i]=1;part[i]=MOD;}fib1[1]=1, fib[1]=1;for(int i=2; i<m; i++){fib1[i]=(fib1[i-1]+fib1[i-2])%MOD;fib[i]=(fib[i-1]+fib1[i])%MOD;}}void eval(int k, int l, int r){if(part[k]<MOD){sum[k]=part[k]*((ll)(r-l));sum[k]%=MOD;if(k<m-1){part[2*k+1]=part[k];part[2*k+2]=part[k];parta[2*k+1]=1;partb[2*k+1]=0;partf[2*k+1]=0;parta[2*k+2]=1;partb[2*k+2]=0;partf[2*k+2]=0;}part[k]=MOD;}if(parta[k]>1 || partb[k]>0 || partf[k]>0){ll s=fib[r-1];if(l>0) s+=(MOD-fib[l-1]);sum[k]=(sum[k]*parta[k]+partb[k]*((ll)(r-l))+partf[k]*s)%MOD;if(k<m-1){ll a1=parta[2*k+1]*parta[k]%MOD;ll b1=(partb[2*k+1]*parta[k]+partb[k])%MOD;ll f1=(partf[2*k+1]*parta[k]+partf[k])%MOD;parta[2*k+1]=a1;partb[2*k+1]=b1;partf[2*k+1]=f1;a1=parta[2*k+2]*parta[k]%MOD;b1=(partb[2*k+2]*parta[k]+partb[k])%MOD;f1=(partf[2*k+2]*parta[k]+partf[k])%MOD;parta[2*k+2]=a1;partb[2*k+2]=b1;partf[2*k+2]=f1;}parta[k]=1;partb[k]=0;partf[k]=0;}}void query(int t, int a, int b, ll x, int k, int l, int r){eval(k, l, r);if(r<=a || b<=l) return;if(a<=l && r<=b){if(t==2){partb[k]+=x;partb[k]%=MOD;}else if(t==3){parta[k]*=x;partb[k]*=x;parta[k]%=MOD;partb[k]%=MOD;}else if(t==4){partf[k]+=x;partf[k]%=MOD;}else{part[k]=x;parta[k]=1;partb[k]=0;partf[k]=0;}eval(k, l, r);}else{query(t, a, b, x, k*2+1, l, (l+r)/2);query(t, a, b, x, k*2+2, (l+r)/2, r);sum[k]=(sum[2*k+1]+sum[2*k+2])%MOD;}}ll getsum(int a, int b, int k, int l, int r){eval(k, l, r);if(b<=l || r<=a){return 0;}if(a<=l && r<=b){return sum[k];}else{return (getsum(a, b, 2*k+1, l, (l+r)/2)+getsum(a, b, 2*k+2, (l+r)/2, r))%MOD;}}int main(){int n, q;cin>>n>>q;init(n);for(int i=0; i<q; i++){int t, l, r; ll k;cin>>t>>l>>r>>k;if(t==0){cout<<k*getsum(l, r+1, 0, 0, m)%MOD<<endl;}else{query(t, l, r+1, k, 0, 0, m);}}return 0;}