beet's soil

競プロのことなど

セグ木に載せるモノイドまとめ(未完)

ネタバレ大量なので注意

要件については↓にまとめてある
beet-aizu.hatenablog.com

はじめに

設計見直したのでこうなった
うし木

template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(int n_){    
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
  }
  T query(int a,int b){
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
};

遅延セグ木

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}
  
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};

具体的には、内部実装が1-indexedになったのとr-lを渡す部分がなくなった。
サイズは必要な時だけモノイド内部でもつことにする。

std::functionは遅いので、ギャグをするとそこそこ速くなる。

template <typename T,typename E, typename F, typename G, typename H>
struct SegmentTree{
  //using F = function<T(T,T)>;
  //using G = function<T(T,E)>;
  //using H = function<E(E,E)>;
:

有名なやつ

和、積、min, max, gcd, lcm
やるだけなのでコードは省略

行列

正方行列ライブラリ:
library/squarematrix.cpp at master · beet-aizu/library · GitHub

atcoder.jp
部分列の数え上げ
グラフ上の経路数の数え上げは行列累乗に帰着される
一点更新 区間積 うし木

  using M = SquareMatrix<unsigned, 6>;
  auto f=[](M a,M b){return M::cross(a,b);};

Submission #4558460 - DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦



atcoder.jp

DAGの数え上げはDPでできる DPをセグ木で高速化
 (T, f) をモノイドとすると、  g(a,b) = f(b,a) としたとき  (T, g) もまたモノイドになる。
結合則だけ示せばよい   g(a,g(b,c)) = g(a,f(c,b)) = f(f(c,b),a) = f(c,f(b,a)) = f(c,g(a,b)) = g(g(a,b),c))
一点更新 区間積 うし木

  using M = Mint<Int>;
  using MM = SquareMatrix<M, 2>;
  auto f=[&](MM a,MM b){return MM::cross(b,a);};

Submission #4558478 - 「みんなのプロコン 2019」決勝

ペアにする

atcoder.jp
indexとペアにする
区間max うし木

    using P = pair<Int, Int>;
    auto f=[&](P a,P b){return max(a,b);};

Submission #4403664 - AtCoder Regular Contest 067



judge.u-aizu.ac.jp
個数とペアにする
区間min/max、区間加算 遅延セグ木

  struct T{
    Int w,x,y,z;
    T(Int w,Int x,Int y,Int z):w(w),x(x),y(y),z(z){}
  };
  
  auto f=[](T a,T b){
           Int cw=min(a.w,b.w);
           Int cx=(a.w==b.w?a.x+b.x:(a.w<b.w?a.x:b.x));
           Int cy=max(a.y,b.y);
           Int cz=(a.y==b.y?a.z+b.z:(a.y>b.y?a.z:b.z));
           return T(cw,cx,cy,cz);
         };
  auto g=[](T a,Int b){
           return T(a.w+b,a.x,a.y+b,a.z);
         };
  auto h=[](Int a,Int b){return a+b;};

AIZU ONLINE JUDGE: Code Review



atcoder.jp
ノードが生きているかとペアにする
区間chmin、区間min 遅延セグ木

  struct T{
    Int val,alive;
    T(Int val,Int alive):val(val),alive(alive){}
  };
  auto f=[](T a,T b){
           return T(min(a.val,b.val),a.alive|b.alive);
         };
  auto g=[](T a,Int b){
           return T(a.alive?min(a.val,b):a.val,a.alive);
         };
  auto h=[](Int a,Int b){return min(a,b);};

Submission #4322642 - 全国統一プログラミング王決定戦本戦



関数の合成

関数  f,g に対し、  g(f(x)) = (g \circ f) (x) がうまく計算できるとき、セグ木に載せられる場合がある。

atcoder.jp
一次関数の合成は一次関数になる うし木

  using P = pair<D, D>;
  auto f=[](P a,P b){
           return P(a.first*b.first,b.first*a.second+b.second);
         };

Submission #4557658 - AtCoder Regular Contest 008



beta.atcoder.jp
正の整数bと非負整数a,cに対し、  f(x) = \left \lfloor \cfrac{x+a}{b} \right \rfloor +c は合成できる。
bをある程度の大きさで制限する必要あり。 遅延セグ木

  using ll = long long;
  struct T{
    ll cur,fst;
    T(ll cur,ll fst):cur(cur),fst(fst){}
  };
  struct E{
    ll r,a,b,c;
    E(ll r,ll a,ll b,ll c):r(r),a(a),b(b),c(c){}
    bool operator==(const E &o) const{
      return r==o.r&&a==o.a&&b==o.b&&c==o.c;
    }
  };

  auto f=[](T a,T b){
           return T(max(a.cur,b.cur),max(a.fst,b.fst));
         };

  auto g=[](T a,E b){
           return T(((b.r?a.fst:a.cur)+b.a)/b.b+b.c,a.fst);
         };

  const ll LIM = 1e9;
  auto h=[](E a,E b){
           if(b.r) return b;
           E c(a.r,a.a+a.b*(a.c+b.a),a.b*b.b,0);
           c.c=c.a/c.b+b.c;
           c.a%=c.b;
           if(c.b>LIM){
             c.a=max(0LL,LIM-(c.b-c.a));
             c.b=LIM;
           }
           return c;
         };

Submission #4557801 - Japan Alumni Group Summer Camp 2018 Day 2



beta.atcoder.jp
 f(x) = \max(x+a, b) は合成できる。
pekempeyさんの解説:
pekempey.hatenablog.com

  using P = pair<ll, ll>;
  auto f=[](P a,P b){
           return P(a.first+b.first,max(a.second+b.first,b.second));
         };

Submission #4558139 - 「みんなのプロコン」



atcoder.jp
区間加算区間GCDはそのままでは処理できない。
階差を取ると区間加算が2箇所の加算になり、元のGCDは階差のGCDと先頭要素のGCDを利用して求められる。

  auto f=[](int a,int b){
           if(a==0&&b==0) return 0;
           if(a==0||b==0) return a?a:b;
           return __gcd(abs(a),abs(b));
         };

Submission #4558398 - AtCoder Regular Contest 017


TODO:書く


judge.u-aizu.ac.jp
RollingHash

judge.u-aizu.ac.jp
二面体群

yukicoder.me
upd, mul, add, fib

yukicoder.me
足し算と掛け算


https://uva.onlinejudge.org/external/131/p13192.pdf
最大値の期待値


beta.atcoder.jp
区間反転、区間最小



yukicoder.me
連続する部分列の和の最大値


codeforces.com
フィボナッチ数を区間に足す、区間


HL分解との組み合わせ

yukicoder.me
一点更新 区間積 うし木

  using M = Mint<int>;
  using MM = SquareMatrix<M, 2>;
  auto f=[](MM a,MM b){return MM::cross(a,b);};

#320087 No.650 行列木クエリ - yukicoder




judge.u-aizu.ac.jp
辺属性のモノイドは端点を持っておく


judge.u-aizu.ac.jp

みんな大好き Do use Segment Tree 連続する部分列の和の最大値