ttamx's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: verify/yosupo/data-structure/link-cut-tree/lazy-link-cut-tree/range_affine_range_sum.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include "template.hpp"
#include "modular-arithmetic/modint.hpp"
#include "data-structure/link-cut-tree/lazy-link-cut-tree.hpp"
#include "group/monoid-action/add-count-affine.hpp"

using mint = mint998;
using Monoid = AddCountMonoid<mint>;
using Action = AddCountAffineAction<mint>;
using T = Monoid::value_type;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    using LCT = LazyLinkCutTree<Action>;
    using Ptr = LCT::Ptr;
    using Node = LCT::Node;
    LCT lct;
    vector<Ptr> ptr(n);
    for(int i=0;i<n;i++){
        mint x;
        cin >> x;
        ptr[i] = new Node(Monoid::make(x));
    }
    for(int i=1;i<n;i++){
        lct.link(ptr[i-1],ptr[i]);
    }
    while(q--){
        int op;
        cin >> op;
        if(op){
            int l,r;
            cin >> l >> r;
            cout << lct.fold(ptr[l],ptr[r-1]).first << "\n";
        }else{
            int l,r,b,c;
            cin >> l >> r >> b >> c;
            lct.apply(ptr[l],ptr[r-1],T(b,c));
        }
    }
}
#line 1 "verify/yosupo/data-structure/link-cut-tree/lazy-link-cut-tree/range_affine_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#line 2 "template.hpp"
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;

const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))

template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}

template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}

int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}

template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
    vector<int> p(SZ(a));
    iota(ALL(p),0);
    stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
    return p;
}

template<class T,size_t D=0>
struct VecBuilder{
    array<size_t,D> d;
    VecBuilder<T,D+1> operator[](size_t n)const{
        VecBuilder<T,D+1> res{};
        for(size_t i=0;i<D;i++)res.d[i]=d[i];
        res.d[D]=n;
        return res;
    }
    template<size_t I=0>
    auto build(const T &x)const{
        if constexpr(I+1==D)return vector<T>(d[I],x);
        else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
    }
    auto operator()(const T &x=T())const{
        static_assert(D>0);
        return build(x);
    }
};
template<class T>
inline constexpr VecBuilder<T> VEC{};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "modular-arithmetic/modint.hpp"

/**
 * Author: Teetat T.
 * Date: 2026-04-15
 * Description: modular arithmetic operations
 */

template<int mod,int root=0>
struct ModInt{
    using mint = ModInt;
    
	static_assert(mod>0,"mod must be positive");

    int x;

    constexpr ModInt():x(0){}
    constexpr ModInt(ll x):x((x%=mod)<0?x+mod:x){}
    constexpr explicit operator int()const{return x;}
    constexpr int val()const{return x;}
    constexpr static int get_mod(){return mod;}
    constexpr static mint get_root(){return mint(root);}
    
    constexpr mint operator-()const{
        mint res;
        res.x=x?mod-x:0;
        return res;
    }
    constexpr mint operator+()const{return *this;}

    constexpr mint inv()const{
        int a=x,b=mod,u=1,v=0,q=0;
        while(b>0){
            q=a/b;
            swap(a-=q*b,b);
            swap(u-=q*v,v);
        }
        return mint(u);
    }
    constexpr mint pow(ll n)const{
        mint res=1,a=*this;
        for(;n>0;a*=a,n>>=1)if(n&1)res*=a;
        return res;
    }
    constexpr mint &operator+=(const mint &o){
        if((x+=o.x)>=mod)x-=mod;
        return *this;
    }
    constexpr mint &operator-=(const mint &o){
        if((x-=o.x)<0)x+=mod;
        return *this;
    }
    constexpr mint &operator*=(const mint &o){
        x=(ll(x)*o.x)%mod;
        return *this;
    }
    constexpr mint &operator/=(const mint &o){
        return *this*=o.inv();
    }

    constexpr mint operator+(const mint &o)const{return mint(*this)+=o;}
    constexpr mint operator-(const mint &o)const{return mint(*this)-=o;}
    constexpr mint operator*(const mint &o)const{return mint(*this)*=o;}
    constexpr mint operator/(const mint &o)const{return mint(*this)/=o;}

    constexpr mint &operator++(){return *this+=mint(1);}
    constexpr mint &operator--(){return *this-=mint(1);}
    constexpr mint operator++(int){mint res=*this;*this+=mint(1);return res;}
    constexpr mint operator--(int){mint res=*this;*this-=mint(1);return res;}
    
    constexpr bool operator==(const mint &o)const{return x==o.x;}
    constexpr bool operator!=(const mint &o)const{return x!=o.x;}
    constexpr bool operator<(const mint &o)const{return x<o.x;}
    
    friend istream &operator>>(istream &is,mint &o){ll x{};is>>x;o=mint(x);return is;}
    friend ostream &operator<<(ostream &os,const mint &o){return os<<o.x;}
};
using mint998 = ModInt<998244353,3>;
using mint107 = ModInt<1000000007>;
#line 2 "data-structure/link-cut-tree/splay-tree-base.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-13
 * Description: Splay Tree. splay(u) will make node u be the root of the tree in amortized O(log n) time.
 */

template<class Node>
struct SplayTreeBase{
    using Ptr = Node*;
    bool is_root(Ptr t){
        return !(t->p)||(t->p->l!=t&&t->p->r!=t);
    } // The parent of the root stores the path parant in link cut tree.
    int size(Ptr t){
        return t?t->size:0;
    }
    virtual void push(Ptr t){};
    virtual void pull(Ptr t){};
    int pos(Ptr t){
        if(t->p){
            if(t->p->l==t)return -1;
            if(t->p->r==t)return 1;
        }
        return 0;
    }
    void rotate(Ptr t){
        Ptr x=t->p,y=x->p;
        if(pos(t)==-1){
            if((x->l=t->r))t->r->p=x;
            t->r=x,x->p=t;
        }else{
            if((x->r=t->l))t->l->p=x;
            t->l=x,x->p=t;
        }
        pull(x),pull(t);
        if((t->p=y)){
            if(y->l==x)y->l=t;
            if(y->r==x)y->r=t;
        }
    }
    void splay(Ptr t){
        if(!t)return;
        push(t);
        while(!is_root(t)){
            Ptr x=t->p;
            if(is_root(x)){
                push(x),push(t);
                rotate(t);
            }else{
                Ptr y=x->p;
                push(y),push(x),push(t);
                if(pos(x)==pos(t))rotate(x),rotate(t);
                else rotate(t),rotate(t);
            }
        }
    }
    void splay_kth(Ptr &t,int k){
        assert(0<=k&&k<size(t));
        while(true){
            push(t);
            if(k<size(t->l))t=t->l;
            else if(size(t->l)==k)break;
            else{
                k-=size(t->l)+1;
                t=t->r;
            }
        }
        splay(t);
    }
    Ptr get_first(Ptr t){
        while(t->l)push(t),t=t->l;
        splay(t);
        return t;
    }
    Ptr get_last(Ptr t){
        while(t->r)push(t),t=t->r;
        splay(t);
        return t;
    }
    Ptr merge(Ptr l,Ptr r){
        splay(l),splay(r);
        if(!l)return r;
        if(!r)return l;
        l=get_last(l);
        l->r=r;
        r->p=l;
        pull(l);
        return l;
    }
    pair<Ptr,Ptr> split(Ptr t,int k){
        if(!t)return {nullptr,nullptr};
        if(k==0)return {nullptr,t};
        if(k==size(t))return {t,nullptr};
        splay_kth(t,k-1);
        Ptr x=t->r;
        t->r=x->p=nullptr;
        pull(t);
        return {t,x};
    }
    void insert(Ptr &t,int k,Ptr v){
        splay(t);
        auto x=split(t,k);
        t=merge(merge(x.first,v),x.second);
    }
    void erase(Ptr &t,int k){
        splay(t);
        auto x=split(t,k);
        auto y=split(x.second,1);
        // delete y.first;
        t=merge(x.first,y.second);
    }
    template<class T>
    Ptr build(const vector<T> &v){
        if(v.empty())return nullptr;
        function<Ptr(int,int)> build=[&](int l,int r){
            if(l==r)return new Node(v[l]);
            int m=(l+r)/2;
            return merge(build(l,m),build(m+1,r));
        };
        return build(0,v.size()-1);
    }
};

#line 2 "data-structure/link-cut-tree/lazy-reversible-bbst.hpp"

/**
 * Author: Teetat Info.
 * Date: 2024-04-13
 * Description: Lazy Reversible BBST Base.
 */

template<class Tree,class Node,class MonoidAction>
struct LazyReversibleBBST:Tree{
    using Tree::merge;
    using Tree::split;
    using typename Tree::Ptr;
    using InfoMonoid = typename MonoidAction::InfoMonoid;
    using TagMonoid = typename MonoidAction::TagMonoid;
    using Info = typename MonoidAction::Info;
    using Tag = typename MonoidAction::Tag;

    LazyReversibleBBST()=default;

    Info sum(Ptr t){
        return t?t->sum:InfoMonoid::unit();
    }
    void pull(Ptr t){
        if(!t)return;
        push(t);
        t->size=1;
        t->sum=t->val;
        t->revsum=t->val;
        if(t->l){
            t->size+=t->l->size;
            t->sum=InfoMonoid::op(t->l->sum,t->sum);
            t->revsum=InfoMonoid::op(t->revsum,t->l->revsum);
        }
        if(t->r){
            t->size+=t->r->size;
            t->sum=InfoMonoid::op(t->sum,t->r->sum);
            t->revsum=InfoMonoid::op(t->r->revsum,t->revsum);
        }
    }
    void push(Ptr t){
        if(!t)return;
        if(t->rev){
            toggle(t->l);
            toggle(t->r);
            t->rev=false;
        }
        if(t->lz!=TagMonoid::unit()){
            propagate(t->l,t->lz);
            propagate(t->r,t->lz);
            t->lz=TagMonoid::unit();
        }
    }
    void toggle(Ptr t){
        if(!t)return;
        swap(t->l,t->r);
        swap(t->sum,t->revsum);
        t->rev^=true;
    }
    void propagate(Ptr t,const Tag &v){
        if(!t)return;
        t->val=MonoidAction::op(t->val,v);
        t->sum=MonoidAction::op(t->sum,v);
        t->revsum=MonoidAction::op(t->revsum,v);
        t->lz=TagMonoid::op(t->lz,v);
    }
    void apply(Ptr &t,int l,int r,const Tag &v){
        if(l>r)return;
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        propagate(y.first,v);
        t=merge(x.first,merge(y.first,y.second));
    }
    Info query(Ptr &t,int l,int r){
        if(l>r)return InfoMonoid::unit();
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        Info res=sum(y.first);
        t=merge(x.first,merge(y.first,y.second));
        return res;
    }
    void reverse(Ptr &t,int l,int r){
        if(l>r)return;
        auto x=split(t,l);
        auto y=split(x.second,r-l+1);
        toggle(y.first);
        t=merge(x.first,merge(y.first,y.second));
    }
};

#line 4 "data-structure/link-cut-tree/lazy-reversible-splay-tree.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-13
 * Description: Lazy Reversible Splay Tree.
 */

template<class MonoidAction>
struct LazyReversibleSplayTreeNode{
    using Ptr = LazyReversibleSplayTreeNode*;
    using InfoMonoid = typename MonoidAction::InfoMonoid;
    using TagMonoid = typename MonoidAction::TagMonoid;
    using Info = typename MonoidAction::Info;
    using Tag = typename MonoidAction::Tag;
    using value_type = Info;
    Ptr l,r,p;
    Info val,sum,revsum;
    Tag lz;
    int size;
    bool rev;
    LazyReversibleSplayTreeNode(const Info &_val=InfoMonoid::unit(),const Tag &_lz=TagMonoid::unit())
        :l(),r(),p(),val(_val),sum(_val),revsum(_val),lz(_lz),size(1),rev(false){}
};

template<class MonoidAction>
struct LazyReversibleSplayTree
    : LazyReversibleBBST<SplayTreeBase<LazyReversibleSplayTreeNode<MonoidAction>>,
      LazyReversibleSplayTreeNode<MonoidAction>,MonoidAction>{
    using Node = LazyReversibleSplayTreeNode<MonoidAction>;
};

#line 2 "data-structure/link-cut-tree/link-cut-tree-base.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-05-19
 * Description: Link Cut Tree Base.
 * Usage:
 *  evert(u): make u be the root of the tree.
 *  link(u,v): attach u to v.
 *  cut(u,v): remove edge between u and v.
 *  get_root(u): get the root of the tree containing u.
 *  lca(u,v): get the lowest common ancestor of u and v.
 *  fold(u,v): get the value of the path from u to v.
 */

template<class Splay>
struct LinkCutTreeBase:Splay{
    using Node = typename Splay::Node;
    using Ptr = Node*;
    using T = typename Node::value_type;
    Ptr expose(Ptr t){
        Ptr pc=nullptr; // preferred child
        for(Ptr cur=t;cur;cur=cur->p){
            this->splay(cur);
            cur->r=pc;
            this->pull(cur);
            pc=cur;
        }
        this->splay(t);
        return pc;
    }
    void evert(Ptr t){ // make t be the root of the tree
        expose(t);
        this->toggle(t);
        this->push(t);
    }
    void link(Ptr u,Ptr v){ // attach u to v
        evert(u);
        expose(v);
        u->p=v;
    }
    void cut(Ptr u,Ptr v){ // cut edge between u and v
        evert(u);
        expose(v);
        assert(u->p==v);
        v->l=u->p=nullptr;
        this->pull(v);
    }
    Ptr get_root(Ptr t){
        expose(t);
        while(t->l)this->push(t),t=t->l;
        this->splay(t);
        return t;
    }
    Ptr lca(Ptr u,Ptr v){
        if(get_root(u)!=get_root(v))return nullptr;
        expose(u);
        return expose(v);
    }
    void set_val(Ptr t,const T &val){
        this->evert(t);
        t->val=val;
        this->pull(t);
    }
    T get_val(Ptr t){
        this->evert(t);
        return t->val;
    }
    T fold(Ptr u,Ptr v){
        evert(u);
        expose(v);
        return v->sum;
    }
};

#line 4 "data-structure/link-cut-tree/lazy-link-cut-tree.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-08-02
 * Description: Lazy Link Cut Tree.
 * Usage: using Lct = LazyLinkCutTree<Action>;
 *  using Ptr = Lct::Ptr;
 *  using Node = Lct::Node;
 *  vector<Ptr> ptr(n);
 *  for(int i=0;i<n;i++)ptr[i]=new Node(val[i]);
 *  auto link=[&](int u,int v){
 *      Lct::link(ptr[u],ptr[v]);
 *  };
 *  auto cut=[&](int u,int v){
 *      Lct::cut(ptr[u],ptr[v]);
 *  };
 *  auto update=[&](int u,int v,const Action::Tag &val){
 *     Lct::apply(ptr[u],ptr[v],val);
 *  };
 *  auto query=[&](int u,int v){
 *     return Lct::fold(ptr[u],ptr[v]);
 *  };
 */

template<class MonoidAction>
struct LazyLinkCutTree:LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>{
    using base = LinkCutTreeBase<LazyReversibleSplayTree<MonoidAction>>;
    using Ptr = typename base::Ptr;
    using Tag = typename MonoidAction::Tag;

    void apply(Ptr u,Ptr v,const Tag &val){
        this->evert(u);
        this->expose(v);
        this->propagate(v,val);
    }
};

#line 2 "group/monoid/affine.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine Transformation Monoid class.
 */

template<class T>
struct AffineMonoid{
    using P = pair<T,T>;
    using value_type = P;
    static constexpr P op(const P &x,const P &y){
        return P(x.first*y.first,x.second*y.first+y.second);
    }
    static constexpr P unit(){return P(T(1),T(0));}
    static constexpr T eval(const P &f,const T &x){
        return f.first*x+f.second;
    }
};

#line 2 "group/monoid/add-count.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Add & Count Monoid class.
 */

template<class T>
struct AddCountMonoid{
    using P = pair<T,ll>;
    using value_type = P;
    static constexpr P op(const P &x,const P &y){
        return P(x.first+y.first,x.second+y.second);
    }
    static constexpr P inverse(const P &x){return P(-x.first,-x.second);}
    static constexpr P unit(){return P(T(0),0LL);}
    static constexpr P make(const T &x){return P(x,1LL);}
};

#line 4 "group/monoid-action/add-count-affine.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine to Add & Count Action class.
 */

template<class T>
struct AddCountAffineAction{
    using InfoMonoid = AddCountMonoid<T>;
    using TagMonoid = AffineMonoid<T>;
    using Info = typename InfoMonoid::value_type;
    using Tag = typename TagMonoid::value_type;
    static constexpr Info op(const Info &a,const Tag &b){
        return Info(a.first*b.first+T(a.second)*b.second,a.second);
    }
};

#line 6 "verify/yosupo/data-structure/link-cut-tree/lazy-link-cut-tree/range_affine_range_sum.test.cpp"

using mint = mint998;
using Monoid = AddCountMonoid<mint>;
using Action = AddCountAffineAction<mint>;
using T = Monoid::value_type;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    using LCT = LazyLinkCutTree<Action>;
    using Ptr = LCT::Ptr;
    using Node = LCT::Node;
    LCT lct;
    vector<Ptr> ptr(n);
    for(int i=0;i<n;i++){
        mint x;
        cin >> x;
        ptr[i] = new Node(Monoid::make(x));
    }
    for(int i=1;i<n;i++){
        lct.link(ptr[i-1],ptr[i]);
    }
    while(q--){
        int op;
        cin >> op;
        if(op){
            int l,r;
            cin >> l >> r;
            cout << lct.fold(ptr[l],ptr[r-1]).first << "\n";
        }else{
            int l,r,b,c;
            cin >> l >> r >> b >> c;
            lct.apply(ptr[l],ptr[r-1],T(b,c));
        }
    }
}
Back to top page