セグメント木を育てる　3

・例題

AOJ_Range Update Query (RUQ)
RMQとの違いは、更新が一点更新ではなく、区間更新となっている点です。
区間なのでセグ木で解けそうですが、区間を更新する際に一つずつ更新するしかなく、O(QN(logN))の計算量がかかります。
N=Q=10^5が最大なので、TLEになります。

・遅延評価セグメント木

上記のような区間更新をO(logN)でできるデータ構造が遅延評価セグメント木です。
https://algo-logic.info/segment-tree/#toc_id_3
ここが分かりやすいいです。

更新の際は必要最低限の区間だけ更新し、必要になった際(次回更新や値の取得時)に必要な個所だけ下に伝播させます。
必要な時に伝播させるため、遅延評価となっています(多分)。

・実装

//0-index
vector<int> segv;
vector<int> sege;
int segv_n;
const int INV_VAL=LLONG_MIN;
void seg_eval(int k){
   if(sege[k]==INV_VAL) return;
   if(k<segv_n){
       sege[k*2+1]=sege[k];
       sege[k*2+2]=sege[k];
   }
   segv[k]=sege[k];
   sege[k]=INV_VAL;
}
void seg_init(int N,int a){
  segv.clear();
  sege.clear();
  int n=1;
  while(n<N) n*=2;
  segv_n=n-1;
  n*=2;
  n=n-1;
  for(int i=0;i<n;i++){
      segv.push_back(a);
      sege.push_back(INV_VAL);
  }
}
void seg_update(int l,int r,int a){
   struct segF{
       static void segupdate(int x,int y,int a,int k,int l,int r){
           seg_eval(k);
           if(r<x||l>y) return;
           if(l>=x&&r<=y) {
               sege[k]=a;
           }
           else{
               segupdate(x,y,a,k*2+1,l,(l+r)/2);
               segupdate(x,y,a,k*2+2,(l+r)/2+1,r);
           }
       }
   };
   segF::segupdate(l,r,a,0,0,segv_n);
}
int seg_find(int x,int y){
  struct segF{
      static int segfind(int x,int y,int k,int l,int r){
          //cout<<x<<","<<y<<","<<k<<","<<l<<","<<r<<endl;
          seg_eval(k);
          if(r<x||l>y) return INV_VAL;
          if(l>=x&&r<=y) return segv[k];
          else{
              int segl=segfind(x,y,k*2+1,l,(l+r)/2);
              int segr=segfind(x,y,k*2+2,(l+r)/2+1,r);
              if(l==x&&r==y) return segv[k];
              if(segl!=INV_VAL) return segl;
              if(segr!=INV_VAL) return segr;
              return INV_VAL;
          }
      }
  };
  return segF::segfind(x,y,0,0,segv_n);
}
void seg_debug(){
  cout<<"---------seg_debug------n="<<segv_n<<endl;
  int k=1;
  for(int i=0;i<(segv_n+1)*2-1;i++){
      if(k==i) {
          cout<<endl;
          k=k*2+1;
      }
      cout<<segv[i]<<","<<sege[i]<<" ";
  }
  cout<<endl<<"------------------------------"<<endl;
}

メインの木(segv)以外に、一旦取っておく用の木(sege)を用意しておきます。

・seg_eval
　segeに保持された値があるなら、その値を下に伝播させる用の関数です。
・seg_init
　segeが増えたため、その分初期化が増えています。
・seg_update
　findと考え方は似ており、最小の区間数でsegeを更新するようにします。
　なお、更新の際に既にsegeに値がある場合は伝播させる必要があります。そうしないと、後から更新した値が、前に更新した値によって上書きされてしまいます。
・seg_find
　ほぼ同じですが、探すときについでに伝播させる必要があります。
・seg_debug
　segeも出力するようにしました。

上記、遅延評価のセグ木を使い、以下のコードを提出しました。

signed main(){
   int n,q;
   cin>>n>>q;
   seg_init(n,pow(2,31)-1);
   for(int i=0;i<q;i++){
       int q;
       cin>>q;
       if(q==0){
           int s,t,x;
           cin>>s>>t>>x;
           seg_update(s,t,x);
       }
       else{
           int x;
           cin>>x;
           cout<<seg_find(x,x)<<endl;
       }
       seg_debug();
   }
}

無事にACです。

・おわりに

ABC177-Fを解くためにセグ木を勉強したので、解いてみたけど無限にバグらせてAC。2日間寝不足になったので諦めました。

あと、Atcoder STL?でセグ木の提供があるとかないとか。
ぬるからは折角なので、自分の育てたセグ木が使いたいですね(愛着もありますし)