data_structure/euler_tour_tree.hpp

View this file on GitHub
Last update: 2020-09-18 16:29:26+09:00
Include: #include "data_structure/euler_tour_tree.hpp"

Code

template<typename T,typename E>
class euler_tour_tree{
	public:
    struct node;
    using np=node*;
	using lint=long long;
    struct node{
        np ch[2]={nullptr,nullptr};
        np p=nullptr;
        int l,r,sz=1,sz2=0;
		T val=et,sum=et;
        E lazy=ee;
        node(){}
        node(int l,int r,int sz2):l(l),r(r),sz2(sz2){}
        bool is_root() {
            return !p;
        }
    };
	vector<hash_map<int,np>>ptr;
	np get_node(int l,int r){
        if(ptr[l].find(r)==ptr[l].end())ptr[l][r]=new node(l,r,l==r);
        return ptr[l][r];
    }
	np root(np t){
		if(!t)return t;
        while(t->p)t=t->p;
        return t;
    }
	bool same(np s,np t){
		return root(s)==root(t);
	}
	bool same(int s,int t){
		return root(get_node(s,s))==root(get_node(t,t));
	}
	np reroot(np t){
        auto s=split(t);
        return merge(s.second,s.first);
    }
	pair<np,np> split(np s){
		splay(s);
		np t=s->ch[0];
		if(t)t->p=nullptr;
		s->ch[0]=nullptr;
		return {t,update(s)};
	}
	pair<np,np> split2(np s){
		splay(s);
		np t=s->ch[0];
		np u=s->ch[1];
		if(t)t->p=nullptr;
		s->ch[0]=nullptr;
		if(u)u->p=nullptr;
		s->ch[1]=nullptr;
		return {t,u};
	}
	tuple<np,np,np> split(np s,np t){
		auto u=split2(s);
		if(same(u.first,t)){
			auto r=split2(t);
			return {r.first,r.second,u.second};
		}else{
			auto r=split2(t);
			return {u.first,r.first,r.second};
		}
	}
	template<typename First, typename... Rest>
	np merge(First s,Rest... t){
		return merge(s,merge(t...));
	}
	np merge(np s,np t){
		while(s->ch[1])s=s->ch[1];
		splay(s);
		s->ch[1]=t;
		if(t)t->p=s;
		return update(s);
	}
    int size(np t){return t?t->sz:0;}
    int size2(np t){return t?t->sz2:0;}
    np update(np t){
        t->sz=size(t->ch[0])+1+size(t->ch[1]);
        t->sz2=size2(t->ch[0])+(t->l==t->r)+size2(t->ch[1]);
		t->sum=et;
		if(t->ch[0])t->sum=fn(t->sum,t->ch[0]->sum);
		if(t->l==t->r)t->sum=fn(t->sum,t->val);
		if(t->ch[1])t->sum=fn(t->sum,t->ch[1]->sum);
		return t;
    }
	void push(np t){
        if(t->lazy!=ee){
            if(t->ch[0])propagate(t->ch[0],t->lazy);
            if(t->ch[1])propagate(t->ch[1],t->lazy);
            t->lazy=ee;
        }
    }
    void propagate(np t,E x){
        t->lazy=g(t->lazy,x);
        t->val=h(t->val,x,1);
        t->sum=h(t->sum,x,t->sz2);
    }
    void set_propagate(np t,E x){
        splay(t);
        propagate(t,x);
        push(t);
    }
    void rot(np t,bool b){
        np x=t->p,y=x->p;
        if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
        t->ch[b]=x,x->p=t;
        update(x);update(t);
        if((t->p=y)){
            if(y->ch[0]==x)y->ch[0]=t;
            if(y->ch[1]==x)y->ch[1]=t;
            update(y);
        }
    }
    void splay(np t){
        push(t);
        while(!t->is_root()){
            np q=t->p;
            if(q->is_root()){
                push(q),push(t);
                rot(t,q->ch[0]==t);
            }else{
                np r=q->p;
                push(r), push(q), push(t);
                bool b=r->ch[0]==q;
                if(q->ch[1-b]==t)rot(q,b),rot(t,b);
                else rot(t,1-b),rot(t,b);
            }
        }
    }
	void debug(np t){
		if(!t)return;
		debug(t->ch[0]);
		cerr<<t->l<<"-"<<t->r<<" ";
		debug(t->ch[1]);
	}
	constexpr static T et=0;
    constexpr static T ee=0;
	constexpr static T fn(T s,T t){
		return s+t;
	}
    constexpr static E g(E s,E t){
		return s+t;
	}
    constexpr static T h(T s,E t,int sz){
		return s+t*sz;
	}
	public:
    void reroot(int s){
        reroot(get_node(s,s));
    }
	void update(int s,T x){
		np t=get_node(s,s);
		splay(t);
		t->val=fn(t->val,x);
		update(t);
	}
    void update_subtree(int p,int v,E x){
        cut(p,v);
		np t=get_node(v,v);
		set_propagate(t,x);
		link(p,v);
    }
	euler_tour_tree(int sz){
		ptr.resize(sz);
		for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i,1);
	}
	bool link(int l,int r){
        if(same(l,r))return 0;
        merge(reroot(get_node(l,l)),get_node(l,r),reroot(get_node(r,r)),get_node(r,l));
        return 1;
    }
	bool cut(int l,int r){
        if(ptr[l].find(r)==ptr[l].end())return 0;
        np s,t,u;
        tie(s,t,u)=split(get_node(l,r),get_node(r,l));
        merge(s,u);
        ptr[l].erase(r);
        ptr[r].erase(l);
        return 1;
    }
	T get_sum(int p,int v){
		cut(p,v);
		np t=get_node(v,v);
		splay(t);
		T res=t->sum;
		link(p,v);
		return res;
	}
};

#line 1 "data_structure/euler_tour_tree.hpp"
template<typename T,typename E>
class euler_tour_tree{
	public:
    struct node;
    using np=node*;
	using lint=long long;
    struct node{
        np ch[2]={nullptr,nullptr};
        np p=nullptr;
        int l,r,sz=1,sz2=0;
		T val=et,sum=et;
        E lazy=ee;
        node(){}
        node(int l,int r,int sz2):l(l),r(r),sz2(sz2){}
        bool is_root() {
            return !p;
        }
    };
	vector<hash_map<int,np>>ptr;
	np get_node(int l,int r){
        if(ptr[l].find(r)==ptr[l].end())ptr[l][r]=new node(l,r,l==r);
        return ptr[l][r];
    }
	np root(np t){
		if(!t)return t;
        while(t->p)t=t->p;
        return t;
    }
	bool same(np s,np t){
		return root(s)==root(t);
	}
	bool same(int s,int t){
		return root(get_node(s,s))==root(get_node(t,t));
	}
	np reroot(np t){
        auto s=split(t);
        return merge(s.second,s.first);
    }
	pair<np,np> split(np s){
		splay(s);
		np t=s->ch[0];
		if(t)t->p=nullptr;
		s->ch[0]=nullptr;
		return {t,update(s)};
	}
	pair<np,np> split2(np s){
		splay(s);
		np t=s->ch[0];
		np u=s->ch[1];
		if(t)t->p=nullptr;
		s->ch[0]=nullptr;
		if(u)u->p=nullptr;
		s->ch[1]=nullptr;
		return {t,u};
	}
	tuple<np,np,np> split(np s,np t){
		auto u=split2(s);
		if(same(u.first,t)){
			auto r=split2(t);
			return {r.first,r.second,u.second};
		}else{
			auto r=split2(t);
			return {u.first,r.first,r.second};
		}
	}
	template<typename First, typename... Rest>
	np merge(First s,Rest... t){
		return merge(s,merge(t...));
	}
	np merge(np s,np t){
		while(s->ch[1])s=s->ch[1];
		splay(s);
		s->ch[1]=t;
		if(t)t->p=s;
		return update(s);
	}
    int size(np t){return t?t->sz:0;}
    int size2(np t){return t?t->sz2:0;}
    np update(np t){
        t->sz=size(t->ch[0])+1+size(t->ch[1]);
        t->sz2=size2(t->ch[0])+(t->l==t->r)+size2(t->ch[1]);
		t->sum=et;
		if(t->ch[0])t->sum=fn(t->sum,t->ch[0]->sum);
		if(t->l==t->r)t->sum=fn(t->sum,t->val);
		if(t->ch[1])t->sum=fn(t->sum,t->ch[1]->sum);
		return t;
    }
	void push(np t){
        if(t->lazy!=ee){
            if(t->ch[0])propagate(t->ch[0],t->lazy);
            if(t->ch[1])propagate(t->ch[1],t->lazy);
            t->lazy=ee;
        }
    }
    void propagate(np t,E x){
        t->lazy=g(t->lazy,x);
        t->val=h(t->val,x,1);
        t->sum=h(t->sum,x,t->sz2);
    }
    void set_propagate(np t,E x){
        splay(t);
        propagate(t,x);
        push(t);
    }
    void rot(np t,bool b){
        np x=t->p,y=x->p;
        if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
        t->ch[b]=x,x->p=t;
        update(x);update(t);
        if((t->p=y)){
            if(y->ch[0]==x)y->ch[0]=t;
            if(y->ch[1]==x)y->ch[1]=t;
            update(y);
        }
    }
    void splay(np t){
        push(t);
        while(!t->is_root()){
            np q=t->p;
            if(q->is_root()){
                push(q),push(t);
                rot(t,q->ch[0]==t);
            }else{
                np r=q->p;
                push(r), push(q), push(t);
                bool b=r->ch[0]==q;
                if(q->ch[1-b]==t)rot(q,b),rot(t,b);
                else rot(t,1-b),rot(t,b);
            }
        }
    }
	void debug(np t){
		if(!t)return;
		debug(t->ch[0]);
		cerr<<t->l<<"-"<<t->r<<" ";
		debug(t->ch[1]);
	}
	constexpr static T et=0;
    constexpr static T ee=0;
	constexpr static T fn(T s,T t){
		return s+t;
	}
    constexpr static E g(E s,E t){
		return s+t;
	}
    constexpr static T h(T s,E t,int sz){
		return s+t*sz;
	}
	public:
    void reroot(int s){
        reroot(get_node(s,s));
    }
	void update(int s,T x){
		np t=get_node(s,s);
		splay(t);
		t->val=fn(t->val,x);
		update(t);
	}
    void update_subtree(int p,int v,E x){
        cut(p,v);
		np t=get_node(v,v);
		set_propagate(t,x);
		link(p,v);
    }
	euler_tour_tree(int sz){
		ptr.resize(sz);
		for(int i=0;i<sz;i++)ptr[i][i]=new node(i,i,1);
	}
	bool link(int l,int r){
        if(same(l,r))return 0;
        merge(reroot(get_node(l,l)),get_node(l,r),reroot(get_node(r,r)),get_node(r,l));
        return 1;
    }
	bool cut(int l,int r){
        if(ptr[l].find(r)==ptr[l].end())return 0;
        np s,t,u;
        tie(s,t,u)=split(get_node(l,r),get_node(r,l));
        merge(s,u);
        ptr[l].erase(r);
        ptr[r].erase(l);
        return 1;
    }
	T get_sum(int p,int v){
		cut(p,v);
		np t=get_node(v,v);
		splay(t);
		T res=t->sum;
		link(p,v);
		return res;
	}
};