cp-library

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

View the Project on GitHub ttamx/cp-library

:heavy_check_mark: verify/yosupo/data-structure/vertex_set_path_composite.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"
#include "template.hpp"
#include "graph/graph-base.hpp"
#include "tree/hld.hpp"
#include "group/monoid/affine.hpp"
#include "group/monoid/monoid-reverse.hpp"
#include "modular-arithmetic/montgomery-modint.hpp"
#include "data-structure/segment-tree/segment-tree.hpp"

using mint = mint998;
using Mon = AffineMonoid<mint>;
using Rev = MonoidReverse<Mon>;
using T = Mon::value_type;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    vector<T> a(n);
    for(auto &[x,y]:a)cin >> x >> y;
    auto g=read_tree(n,0);
    HLD hld(g);
    auto b=a;
    for(int i=0;i<n;i++)a[hld.tin[i]]=b[i];
    SegmentTree<Mon> s(a);
    SegmentTree<Rev> sr(a);
    while(q--){
        int op;
        cin >> op;
        if(op==0){
            int p;
            mint x,y;
            cin >> p >> x >> y;
            s.modify(hld.tin[p],T(x,y));
            sr.modify(hld.tin[p],T(x,y));
        }else{
            int u,v;
            cin >> u >> v;
            mint x;
            cin >> x;
            for(auto [u,v]:hld.get_path(u,v,true,false)){
                if(u<=v){
                    x=Mon::eval(s.query(u,v),x);
                }else{
                    x=Mon::eval(sr.query(v,u),x);
                }
            }
            cout << x << "\n";
        }
    }
}
#line 1 "verify/yosupo/data-structure/vertex_set_path_composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

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

/**
 * Author: Teetat T.
 * Date: 2024-06-15
 * Description: Graph Base
 */

template<class T>
struct Edge{
    int from,to,id;
    T cost;
    Edge(int _from,int _to,T _cost,int _id):from(_from),to(_to),cost(_cost),id(_id){}
    operator int()const{return to;}
};

template<class T=void,bool directed=false>
struct Graph{
    static constexpr bool is_directed=directed;
    static constexpr bool is_weighted=!is_same<T,void>::value;
    using cost_type = std::conditional_t<is_weighted,T,int>;
    using edge_type = Edge<cost_type>;
    int n,m;
    vector<edge_type> edges;
    vector<vector<edge_type>> g;
    vector<int> _deg,_indeg,_outdeg;
    Graph():n(0),m(0){}
    Graph(int _n):n(_n),m(0),g(_n){}
    vector<edge_type> &operator[](int u){return g[u];}
    void add_edge(int from,int to,cost_type cost=1,int id=-1){
        assert(0<=from&&from<n&&0<=to&&to<n);
        if(id==-1)id=m;
        edges.emplace_back(edge_type(from,to,cost,id));
        g[from].emplace_back(edge_type(from,to,cost,id));
        if(!is_directed)g[to].emplace_back(edge_type(to,from,cost,id));
        m++;
    }
    void calc_deg(){
        _deg.assign(n,0);
        for(auto &e:edges)_deg[e.from]++,_deg[e.to]++;
    }
    void calc_inout_deg(){
        _indeg.assign(n,0);
        _outdeg.assign(n,0);
        for(auto &e:edges)_outdeg[e.from]++,_indeg[e.to]++;
    }
    const vector<int> &deg_array(){
        if(_deg.empty())calc_deg();
        return _deg;
    }
    const vector<int> &indeg_array(){
        if(_indeg.empty())calc_inout_deg();
        return _indeg;
    }
    const vector<int> &outdeg_array(){
        if(_outdeg.empty())calc_inout_deg();
        return _outdeg;
    }
    int deg(int u){return deg_array()[u];}
    int indeg(int u){return indeg_array()[u];}
    int outdeg(int u){return outdeg_array()[u];}
    Graph reverse(){
        assert(is_directed);
        Graph res(n);
        for(auto &e:edges)res.add_edge(e.to,e.from,e.cost,e.id);
        return res;
    }
};

template<class T=void,bool directed=false>
Graph<T,directed> read_graph(int n,int m,int offset=1){
    using G = Graph<T,directed>;
    G g(n);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        u-=offset,v-=offset;
        if(g.is_weighted){
            typename G::cost_type w;
            cin >> w;
            g.add_edge(u,v,w);
        }else{
            g.add_edge(u,v);
        }
    }
    return g;
}
template<class T=void,bool directed=false>
Graph<T,directed> read_tree(int n,int offset=1){
    return read_graph<T,directed>(n,n-1,offset);
}

#line 2 "tree/hld.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-15
 * Description: Heavy-Light Decomposition.
 */

template<class G>
struct HLD{
    int n;
    G &g;
    int root,timer;
    vector<int> par,sz,dep,hv,head,tin,tout,ord;
    HLD(G &_g,int _root=0)
        : n(_g.n),g(_g),root(_root),timer(-1),par(n,root),sz(n,1),
          dep(n),hv(n,-1),head(n),tin(n),tout(n),ord(n){
        par[0]=-1;
        dfs_sz(root);
        dfs_hld(root);
    }
    void dfs_sz(int u){
        for(int v:g[u])if(v!=par[u]){
            par[v]=u;
            dep[v]=dep[u]+1;
            dfs_sz(v);
            sz[u]+=sz[v];
            if(hv[u]==-1||sz[v]>sz[hv[u]])hv[u]=v;
        }
    }
    void dfs_hld(int u){
        tin[u]=++timer;
        ord[timer]=u;
        if(hv[u]!=-1){
            head[hv[u]]=head[u];
            dfs_hld(hv[u]);
        }
        for(int v:g[u])if(v!=par[u]&&v!=hv[u]){
            head[v]=v;
            dfs_hld(v);
        }
        tout[u]=timer;
    }
    vector<pair<int,int>> get_path(int u,int v,bool vertex,bool commutative=true){
        vector<pair<int,int>> up,down;
        while(head[u]!=head[v]){
            if(dep[head[u]]>dep[head[v]]){
                up.emplace_back(tin[head[u]],tin[u]);
                u=par[head[u]];
            }else{
                down.emplace_back(tin[head[v]],tin[v]);
                v=par[head[v]];
            }
        }
        if(dep[u]>dep[v])up.emplace_back(tin[v]+1,tin[u]),u=v;
        else if(u!=v)down.emplace_back(tin[u]+1,tin[v]),v=u;
        if(vertex)up.emplace_back(tin[u],tin[u]);
        reverse(down.begin(),down.end());
        if(!commutative)for(auto &[x,y]:up)swap(x,y);
        up.insert(up.end(),down.begin(),down.end());
        return up;
    }
    int lca(int u,int v){
        while(head[u]!=head[v]){
            if(dep[head[u]]>dep[head[v]])swap(u,v);
            v=par[head[v]];
        }
        return dep[u]<dep[v]?u:v;
    }
    int dist(int u,int v){
        return dep[u]+dep[v]-2*dep[lca(u,v)];
    }
    int jump(int u,int v,int k){
        int w=lca(u,v);
        int d=dep[u]+dep[v]-2*dep[w];
        if(k>d)return -1;
        if(k>dep[u]-dep[w]){
            k=d-k;
            swap(u,v);
        }
        while(k>=dep[u]-dep[head[u]]+1){
            k-=dep[u]-dep[head[u]]+1;
            u=par[head[u]];
        }
        return ord[tin[u]-k];
    }
    bool is_ancestor(int u,int v){
        return tin[u]<=tin[v]&&tout[v]<=tout[u];
    }
};

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

/**
 * Author: Teetat T.
 * Date: 2024-04-14
 * Description: Affine Transfomation 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/monoid-reverse.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-16
 * Description: Monoid Reverse class.
 */

template<class Monoid>
struct MonoidReverse{
    using value_type = typename Monoid::value_type;
    static constexpr value_type op(const value_type &x,const value_type &y){return Monoid::op(y,x);}
    static constexpr value_type unit(){return Monoid::unit();}
};

#line 2 "modular-arithmetic/montgomery-modint.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-03-17
 * Description: modular arithmetic operators using Montgomery space
 */

template<uint32_t mod,uint32_t root=0>
struct MontgomeryModInt{
    using mint = MontgomeryModInt;
    using i32 = int32_t;
    using u32 = uint32_t;
    using u64 = uint64_t;

    static constexpr u32 get_r(){
        u32 res=1;
        for(i32 i=0;i<5;i++)res*=2-mod*res;
        return res;
    }

    static const u32 r=get_r();
    static const u32 n2=-u64(mod)%mod;
    static_assert(mod<(1<<30));
    static_assert((mod&1)==1);
    static_assert(r*mod==1);

    u32 x;

    constexpr MontgomeryModInt():x(0){}
    constexpr MontgomeryModInt(const int64_t &v):x(reduce(u64(v%mod+mod)*n2)){}

    static constexpr u32 get_mod(){return mod;}
    static constexpr mint get_root(){return mint(root);}
    explicit constexpr operator int64_t()const{return val();}

    static constexpr u32 reduce(const u64 &v){
        return (v+u64(u32(v)*u32(-r))*mod)>>32;
    }

    constexpr u32 val()const{
        u32 res=reduce(x);
        return res>=mod?res-mod:res;
    }

    constexpr mint inv()const{
        int a=val(),b=mod,u=1,v=0,q=0;
        while(b>0){
            q=a/b;
            a-=q*b;
            u-=q*v;
            swap(a,b);
            swap(u,v);
        }
        return mint(u);
    }

    constexpr mint &operator+=(const mint &rhs){
        if(i32(x+=rhs.x-2*mod)<0)x+=2*mod;
        return *this;
    }
    constexpr mint &operator-=(const mint &rhs){
        if(i32(x-=rhs.x)<0)x+=2*mod;
        return *this;
    }
    constexpr mint &operator*=(const mint &rhs){
        x=reduce(u64(x)*rhs.x);
        return *this;
    }
    constexpr mint &operator/=(const mint &rhs){
        return *this*=rhs.inv();
    }

    constexpr mint &operator++(){return *this+=mint(1);}
    constexpr mint &operator--(){return *this-=mint(1);}
    constexpr mint operator++(int){
        mint res=*this;
        return *this+=mint(1),res;
    }
    constexpr mint operator--(int){
        mint res=*this;
        return *this-=mint(1),res;
    }

    constexpr mint operator-()const{return mint()-mint(*this);};
    constexpr mint operator+()const{return mint(*this);};

    friend constexpr mint operator+(const mint &lhs,const mint &rhs){return mint(lhs)+=rhs;}
    friend constexpr mint operator-(const mint &lhs,const mint &rhs){return mint(lhs)-=rhs;}
    friend constexpr mint operator*(const mint &lhs,const mint &rhs){return mint(lhs)*=rhs;}
    friend constexpr mint operator/(const mint &lhs,const mint &rhs){return mint(lhs)/=rhs;}
    friend constexpr bool operator==(const mint &lhs,const mint &rhs){
        return (lhs.x>=mod?lhs.x-mod:lhs.x)==(rhs.x>=mod?rhs.x-mod:rhs.x);
    }
    friend constexpr bool operator!=(const mint &lhs,const mint &rhs){
        return (lhs.x>=mod?lhs.x-mod:lhs.x)!=(rhs.x>=mod?rhs.x-mod:rhs.x);
    }
    friend constexpr bool operator<(const mint &lhs,const mint &rhs){
        return (lhs.x>=mod?lhs.x-mod:lhs.x)<(rhs.x>=mod?rhs.x-mod:rhs.x); // for std::map
    }

    friend istream &operator>>(istream &is,mint &o){
        int64_t v;
        is >> v;
        o=mint(v);
        return is;
    }
    friend ostream &operator<<(ostream &os,const mint &o){
        return os << o.val();
    }
};
using mint998 = MontgomeryModInt<998244353,3>;
using mint107 = MontgomeryModInt<1000000007>;

#line 2 "data-structure/segment-tree/segment-tree.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-01-15
 * Description: Segment Tree
 */

template<class Monoid>
struct SegmentTree{
    using T = typename Monoid::value_type;
    int n;
    vector<T> t;
    SegmentTree(){}
    SegmentTree(int n,function<T(int)> create){init(n,create);}
    SegmentTree(int n,T v=Monoid::unit()){init(n,[&](int){return v;});}
    template<class U>
    SegmentTree(const vector<U> &a){init((int)a.size(),[&](int i){return T(a[i]);});}
    void init(int _n,function<T(int)> create){
        n=_n;
        t.assign(4<<(31-__builtin_clz(n)),Monoid::unit());
        function<void(int,int,int)> build=[&](int l,int r,int i){
            if(l==r)return void(t[i]=create(l));
            int m=(l+r)/2;
            build(l,m,i*2);
            build(m+1,r,i*2+1);
            pull(i);
        };
        build(0,n-1,1);
    }
    void pull(int i){
        t[i]=Monoid::op(t[i*2],t[i*2+1]);
    }
    void modify(int l,int r,int i,int x,const T &v){
        if(x<l||r<x)return;
        if(l==r)return void(t[i]=v);
        int m=(l+r)/2;
        modify(l,m,i*2,x,v);
        modify(m+1,r,i*2+1,x,v);
        pull(i);
    }
    void modify(int x,const T &v){
        modify(0,n-1,1,x,v);
    }
    template<class U>
    void update(int l,int r,int i,int x,const U &v){
        if(x<l||r<x)return;
        if(l==r)return void(t[i]=Monoid::op(t[i],v));
        int m=(l+r)/2;
        update(l,m,i*2,x,v);
        update(m+1,r,i*2+1,x,v);
        pull(i);
    }
    template<class U>
    void update(int x,const U &v){
        update(0,n-1,1,x,v);
    }
    T query(int l,int r,int i,int x,int y){
        if(y<l||r<x)return Monoid::unit();
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return Monoid::op(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
    T query(int x,int y){
        return query(0,n-1,1,x,y);
    }
    template<class F>
    int findfirst(int l,int r,int i,int x,int y,const F &f){
        if(y<l||r<x||!f(t[i]))return n;
        if(l==r)return l;
        int m=(l+r)/2;
        int res=findfirst(l,m,i*2,x,y,f);
        if(res==n)res=findfirst(m+1,r,i*2+1,x,y,f);
        return res;
    }
    template<class F>
    int findfirst(int x,int y,const F &f){
        return findfirst(0,n-1,1,x,y,f);
    }
    template<class F>
    int findlast(int l,int r,int i,int x,int y,const F &f){
        if(y<l||r<x||!f(t[i]))return -1;
        if(l==r)return l;
        int m=(l+r)/2;
        int res=findlast(m+1,r,i*2+1,x,y,f);
        if(res==-1)res=findlast(l,m,i*2,x,y,f);
        return res;
    }
    template<class F>
    int findlast(int x,int y,const F &f){
        return findlast(0,n-1,1,x,y,f);
    }
};

#line 9 "verify/yosupo/data-structure/vertex_set_path_composite.test.cpp"

using mint = mint998;
using Mon = AffineMonoid<mint>;
using Rev = MonoidReverse<Mon>;
using T = Mon::value_type;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    vector<T> a(n);
    for(auto &[x,y]:a)cin >> x >> y;
    auto g=read_tree(n,0);
    HLD hld(g);
    auto b=a;
    for(int i=0;i<n;i++)a[hld.tin[i]]=b[i];
    SegmentTree<Mon> s(a);
    SegmentTree<Rev> sr(a);
    while(q--){
        int op;
        cin >> op;
        if(op==0){
            int p;
            mint x,y;
            cin >> p >> x >> y;
            s.modify(hld.tin[p],T(x,y));
            sr.modify(hld.tin[p],T(x,y));
        }else{
            int u,v;
            cin >> u >> v;
            mint x;
            cin >> x;
            for(auto [u,v]:hld.get_path(u,v,true,false)){
                if(u<=v){
                    x=Mon::eval(s.query(u,v),x);
                }else{
                    x=Mon::eval(sr.query(v,u),x);
                }
            }
            cout << x << "\n";
        }
    }
}
Back to top page