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

ネタバレ大量なので注意

はじめに

要件については↓にまとめてある
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
やるだけなのでコードは省略

行列

正方行列ライブラリ：
github.com

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3035judge.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
judge.yosupo.jp

beta.atcoder.jp
正の整数bと非負整数a,cに対し、 $f (x) = ⌊ \frac{x + a}{b} ⌋ + 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

yukicoder.me
区間二乗和
二乗和、線形和、個数を持ってえい

  using T = tuple<Int, Int, Int>;
  auto f=[](T a,T b){
    auto [ax,ay,az]=a;
    auto [bx,by,bz]=b;
    return T(ax+bx,ay+by,az+bz);
  };
  auto g=[](T a,Int b){
    auto [ax,ay,az]=a;
    return T(ax+2*ay*b+az*b*b,ay+az*b,az);
  };
  auto h=[](Int a,Int b){return a+b;};

yukicoder.me

TODO：書く

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0355judge.u-aizu.ac.jp
RollingHash

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0390judge.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 (C++17(1z)) No.650 行列木クエリ - yukicoder

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0367judge.u-aizu.ac.jp
辺属性のモノイドは端点を持っておく

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450judge.u-aizu.ac.jp

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

beet's soil

競プロのことなど（近々削除予定）

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

はじめに

はじめに

有名なやつ

行列

ペアにする

関数の合成

HL分解との組み合わせ