結果

問題 No.749 クエリ全部盛り
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2018-10-07 00:49:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,786 ms / 3,000 ms
コード長 3,059 bytes
コンパイル時間 881 ms
コンパイル使用メモリ 76,668 KB
最終ジャッジ日時 2025-01-06 14:24:29
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:142:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  142 |   scanf("%d%d",&n,&q);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:145:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  145 |     scanf("%d%d%d%d",&kind,&l,&r,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cassert>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
typedef pair<lint,lint>pll;
#define rep(i,n)for(int i=0;i<(int)(n);++i)
const lint mo=1e9+7;

const int N=1000000;
const int A=1000;
const int B=N/A;
lint a[N];
lint asum[A];
lint u[A],v[A];
lint tap[A];
pll phi[N];
pll phiacc[N+1];
pll add(pll a,pll b){
  return pll((a.first+b.first)%mo,(a.second+b.second)%mo);
}
pll mul(pll a,pll b){
  lint x=a.first*b.first+5*a.second*b.second;
  lint y=a.first*b.second+a.second*b.first;
  return pll(x%mo,y%mo);
}

void init(){
  pll p((mo+1)/2,(mo+1)/2);
  pll c(1,0);
  rep(i,N){
    phi[i]=c;
    phiacc[i+1]=add(phiacc[i],phi[i]);
    c=mul(c,p);
  }
}

void red(int k){
  if(k>=A)return;
  lint tmp=0;
  rep(i,B){
    int idx=k*B+i;
    a[idx]=u[k]*a[idx]+v[k]+2*tap[k]*phi[idx].second;
    a[idx]%=mo;
    tmp=(tmp+a[idx])%mo;
  }
  u[k]=1;
  v[k]=0;
  tap[k]=0;
  asum[k]=tmp;
}
void upd_n_sx_plus_t(int l,int r,int s,int t){
  assert(r<=l/B*B+B);
  if(l>=r)return;
  red(l/B);
  lint tmp=asum[l/B];
  for(int i=l;i<r;i++){
    tmp+=mo-a[i];
    a[i]=(a[i]*s+t)%mo;
    tmp+=a[i];
  }
  asum[l/B]=tmp%mo;
}
void upd_sx_plus_t(int l,int r,int s,int t){
  assert(l<=r);
  int lb=(l+B-1)/B;
  int rb=r/B;
  if(lb>rb){
    upd_n_sx_plus_t(l,r,s,t);
    return;
  }
  upd_n_sx_plus_t(l,B*lb,s,t);
  upd_n_sx_plus_t(B*rb,r,s,t);
  for(int i=lb;i<rb;++i){
    u[i]=u[i]*s%mo;
    v[i]=(v[i]*s+t)%mo;
    tap[i]=tap[i]*s%mo;
  }
}
void upd_n_fib(int l,int r,int k){
  assert(r<=l/B*B+B);
  if(l>=r)return;
  red(l/B);
  lint tmp=asum[l/B];
  for(int i=l;i<r;i++){
    tmp+=mo-a[i];
    a[i]=(a[i]+2*phi[i].second*k)%mo;
    tmp+=a[i];
  }
  asum[l/B]=tmp%mo;
}
void upd_fib(int l,int r,int k){
  assert(l<=r);
  int lb=(l+B-1)/B;
  int rb=r/B;
  if(lb>rb){
    upd_n_fib(l,r,k);
    return;
  }
  upd_n_fib(l,B*lb,k);
  upd_n_fib(B*rb,r,k);
  for(int i=lb;i<rb;++i){
    tap[i]=(tap[i]+k)%mo;
  }
}

lint calc_n(int l,int r){
  assert(r<=l/B*B+B);
  if(l>=r)return 0;
  red(l/B);
  lint ans=0;
  for(int i=l;i<r;i++)ans=(ans+a[i])%mo;
  return ans;
}

lint calc(int l,int r){
  assert(l<=r);
  int lb=(l+B-1)/B;
  int rb=r/B;
  if(lb>rb){
    return calc_n(l,r);
  }
  lint ans=0;
  ans=calc_n(l,B*lb);
  ans+=calc_n(B*rb,r);
  for(int i=lb;i<rb;++i){
    ans+=u[i]*asum[i]%mo;
    ans+=v[i]*B;
    ans+=2*tap[i]*(phiacc[i*B+B].second-phiacc[i*B].second+mo)%mo;
    ans%=mo;
  }
  return ans;
}

int main(){
  init();
  int n,q;
  scanf("%d%d",&n,&q);
  rep(_,q){
    int kind,l,r,k;
    scanf("%d%d%d%d",&kind,&l,&r,&k);
    r++;
    assert(kind>=0);
    assert(kind<=4);
    assert(l<r);
    assert(k>=0);
    assert(k<=1e9);
    switch(kind){
    case 0:
      printf("%lld\n",k*calc(l,r)%mo);
      break;
    case 1:
      upd_sx_plus_t(l,r,0,k);
      break;
    case 2:
      upd_sx_plus_t(l,r,1,k);
      break;
    case 3:
      upd_sx_plus_t(l,r,k,0);
      break;
    case 4:
      upd_fib(l,r,k);
      break;
    }
  }
}
0