52 C Circular RMQ

問題

n個からなる配列a[i]が与えられる。
次のm個クエリに答えよ。

  • l,r : a[l]からa[r]の最小値を出力する
  • l,r,v : a[l]からa[r]に一様にvを加算する

ただし、配列は円環状になっており、a[n-1]の右の要素はa[0]である。

制約条件

v≦10^6
n≦2000000

方針

セグメント木によるRMQ + 区間に対する一様な加算


蟻本の通常のセグメント木によるRMQの実装に加えて、
各節点に対して一様に加算される値を持っておく。
queryや値の更新の際には、(両方の子の最小値)+節点に加算される値を答えとして返す。

ソースコード

const int MAX=1<<18;
int n,mn[2*MAX-1],ad[2*MAX-1];
void init(int n_){
  n=1;
  while(n<n_)n*=2;
  rep(i,2*n-1)mn[i]=ad[i]=0;
}
int query(int a,int b,int k,int l,int r){
  if(r<=a||b<=l)return 1e9;
  if(a<=l&&r<=b)return ad[k]+mn[k];
  return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r))+ad[k];
}
void add(int a,int b,int k,int l,int r,int v){
  if(r<=a||b<=l)return;
  if(a<=l&&r<=b){
    ad[k]+=v;
    while(k>0){
      k=(k-1)/2;
      mn[k]=min(mn[2*k+1]+ad[2*k+1],mn[2*k+2]+ad[2*k+2]);
    }
  }
  else{
    add(a,b,k*2+1,l,(l+r)/2,v); add(a,b,k*2+2,(l+r)/2,r,v);
  }
}

void run(){
  int m,q; cin>>m; init(m);
  rep(i,m){
    int a; cin>>a;
    add(i,i+1,0,0,n,a);
  }
  cin>>q; cin.ignore();
  rep(i,q){
    string s; getline(cin,s);
    stringstream ss(s);
    int a[3],k=0;
    while(ss>>a[k])k++;
    
    if(k==2){
      int ans;
      if(a[0]>a[1])ans=min(query(0,a[1]+1,0,0,n),query(a[0],m,0,0,n));
      else ans=query(a[0],a[1]+1,0,0,n);
      cout<<ans<<endl;
    }
    else{
      if(a[0]>a[1])add(0,a[1]+1,0,0,n,a[2]),add(a[0],m,0,0,n,a[2]);
      else add(a[0],a[1]+1,0,0,n,a[2]);
    }
  }
}