This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tko919/library
#include "DataStructure/sortablesegtree.hpp"
#pragma once #include "DataStructure/segtree.hpp" template<typename M,typename N,M (*f)(M,M),M (*g)(M,N),M (*m1)(),int LG=30>struct SortableSegmentTree{ SortableSegmentTree(){} SortableSegmentTree(vector<int>& ks,vector<M>& vs):n(ks.size()),seg(n),Es(n){ rep(i,0,n){ Ls.insert(i); Es[i]=new Elem(ks[i],vs[i]); seg.set(i,vs[i]); } Ls.insert(n); } void update(int i,int key,M val){ split(i); split(i+1); Es[i]=new Elem(key,val); seg.set(i,val); } M query(int L,int R){ split(L); split(R); return seg.query(L,R); } void sort(int L,int R,bool rev=false){ split(L); split(R); int pos=L; for(;;){ pos=*(Ls.upper_bound(pos)); if(pos>=R)break; Es[L]=meld(Es[L],Es[pos]); Es[pos]=new Elem(); seg.set(pos,m1()); Ls.erase(pos); } Es[L]->set(rev); seg.set(L,Es[L]->value()); } private: struct Trie{ Trie *cp[2]; int sz; M val,lav; Trie(){cp[0]=cp[1]=nullptr;} Trie(int key,M v){cp[0]=cp[1]=nullptr,init(key,v);} void init(int key,M v,int lg=LG){ sz=1; val=lav=v; if(lg==-1)return; if(!cp[key>>lg&1])cp[key>>lg&1]=new Trie(); cp[key>>lg&1]->init(key,v,lg-1); } void update(){ if(!cp[0] and !cp[1])return; sz=0; val=lav=m1(); if(cp[0]){ sz+=cp[0]->sz; val=f(val,cp[0]->val); lav=f(cp[0]->lav,lav); } if(cp[1]){ sz+=cp[1]->sz; val=f(val,cp[1]->val); lav=f(cp[1]->lav,lav); } } void apply(N x){ assert(sz==1); val=lav=g(val,x); if(cp[0])cp[0]->apply(x); if(cp[1])cp[1]->apply(x); } }; using Tp=Trie*; int sz(Tp t){return t?t->sz:0;} Tp meld(Tp a,Tp b){ if(!a)return b; if(!b)return a; a->cp[0]=meld(a->cp[0],b->cp[0]); a->cp[1]=meld(a->cp[1],b->cp[1]); a->update(); return a; } pair<Tp,Tp> split(Tp t,int k){ if(k==0)return {nullptr,t}; if(k==sz(t))return {t,nullptr}; if(k<sz(t->cp[0])){ auto [l,tmp]=split(t->cp[0],k); auto L=new Trie(); L->cp[0]=l; L->update(); auto R=new Trie(); R->cp[0]=tmp,R->cp[1]=t->cp[1]; R->update(); return {L,R}; } else{ auto [tmp,r]=split(t->cp[1],k-sz(t->cp[0])); auto L=new Trie(); auto R=new Trie(); L->cp[0]=t->cp[0],L->cp[1]=tmp; L->update(); R->cp[1]=r; R->update(); return {L,R}; } } struct Elem{ Tp node; bool rev; Elem():node(nullptr),rev(0){} Elem(int key,M x):node(new Trie(key,x)),rev(0){} Elem(Tp t,bool r):node(t),rev(r){} void set(bool r){rev=r;} void apply(N x){node->apply(x);} M value(){return rev?node->lav:node->val;} }; using Ep=Elem*; Ep meld(Ep s,Ep t){ return new Elem(meld(s->node,t->node),0); } pair<Ep,Ep> split(Ep t,int k){ if(t->rev)k=sz(t->node)-k; auto [L,R]=split(t->node,k); if(t->rev)swap(L,R); auto LE=new Elem(L,t->rev); auto RE=new Elem(R,t->rev); return {LE,RE}; } const int n; SegmentTree<M,N,f,g,m1> seg; set<int> Ls; vector<Ep> Es; void split(int k){ if(k>=n)return; int pos=*(--Ls.upper_bound(k)); if(pos==k)return; auto [L,R]=split(Es[pos],k-pos); Es[pos]=L,Es[k]=R; seg.set(pos,Es[pos]->value()); seg.set(k,Es[k]->value()); Ls.insert(k); } }; /** * @brief Sortable Segment Tree */
#line 2 "DataStructure/segtree.hpp" template<typename M,typename N,M (*f)(M,M),M (*g)(M,N),M (*m1)()>struct SegmentTree{ int n; vector<M> data; SegmentTree(int _n=0){ n=1; while(n<_n)n<<=1; data.assign(2*n,m1()); } void run(vector<M>& v){ for(int i=0;i<(int)v.size();i++)data[i+n]=v[i]; for(int k=n-1;k>0;k--)data[k]=f(data[2*k],data[2*k+1]); } void set(int k,const M &x){ k+=n; data[k]=x; while(k>>=1)data[k]=f(data[2*k],data[2*k+1]); } void update(int k,const N &x){ k+=n; data[k]=g(data[k],x); while(k>>=1)data[k]=f(data[2*k],data[2*k+1]); } M query(int a,int b){ M L=m1(),R=m1(); for(a+=n,b+=n;a<b;a>>=1,b>>=1){ if(a&1)L=f(L,data[a++]); if(b&1)R=f(data[--b],R); } return f(L,R); } M operator[](const int &k)const{return data[k+n];} }; /** * @brief Segment Tree */ #line 3 "DataStructure/sortablesegtree.hpp" template<typename M,typename N,M (*f)(M,M),M (*g)(M,N),M (*m1)(),int LG=30>struct SortableSegmentTree{ SortableSegmentTree(){} SortableSegmentTree(vector<int>& ks,vector<M>& vs):n(ks.size()),seg(n),Es(n){ rep(i,0,n){ Ls.insert(i); Es[i]=new Elem(ks[i],vs[i]); seg.set(i,vs[i]); } Ls.insert(n); } void update(int i,int key,M val){ split(i); split(i+1); Es[i]=new Elem(key,val); seg.set(i,val); } M query(int L,int R){ split(L); split(R); return seg.query(L,R); } void sort(int L,int R,bool rev=false){ split(L); split(R); int pos=L; for(;;){ pos=*(Ls.upper_bound(pos)); if(pos>=R)break; Es[L]=meld(Es[L],Es[pos]); Es[pos]=new Elem(); seg.set(pos,m1()); Ls.erase(pos); } Es[L]->set(rev); seg.set(L,Es[L]->value()); } private: struct Trie{ Trie *cp[2]; int sz; M val,lav; Trie(){cp[0]=cp[1]=nullptr;} Trie(int key,M v){cp[0]=cp[1]=nullptr,init(key,v);} void init(int key,M v,int lg=LG){ sz=1; val=lav=v; if(lg==-1)return; if(!cp[key>>lg&1])cp[key>>lg&1]=new Trie(); cp[key>>lg&1]->init(key,v,lg-1); } void update(){ if(!cp[0] and !cp[1])return; sz=0; val=lav=m1(); if(cp[0]){ sz+=cp[0]->sz; val=f(val,cp[0]->val); lav=f(cp[0]->lav,lav); } if(cp[1]){ sz+=cp[1]->sz; val=f(val,cp[1]->val); lav=f(cp[1]->lav,lav); } } void apply(N x){ assert(sz==1); val=lav=g(val,x); if(cp[0])cp[0]->apply(x); if(cp[1])cp[1]->apply(x); } }; using Tp=Trie*; int sz(Tp t){return t?t->sz:0;} Tp meld(Tp a,Tp b){ if(!a)return b; if(!b)return a; a->cp[0]=meld(a->cp[0],b->cp[0]); a->cp[1]=meld(a->cp[1],b->cp[1]); a->update(); return a; } pair<Tp,Tp> split(Tp t,int k){ if(k==0)return {nullptr,t}; if(k==sz(t))return {t,nullptr}; if(k<sz(t->cp[0])){ auto [l,tmp]=split(t->cp[0],k); auto L=new Trie(); L->cp[0]=l; L->update(); auto R=new Trie(); R->cp[0]=tmp,R->cp[1]=t->cp[1]; R->update(); return {L,R}; } else{ auto [tmp,r]=split(t->cp[1],k-sz(t->cp[0])); auto L=new Trie(); auto R=new Trie(); L->cp[0]=t->cp[0],L->cp[1]=tmp; L->update(); R->cp[1]=r; R->update(); return {L,R}; } } struct Elem{ Tp node; bool rev; Elem():node(nullptr),rev(0){} Elem(int key,M x):node(new Trie(key,x)),rev(0){} Elem(Tp t,bool r):node(t),rev(r){} void set(bool r){rev=r;} void apply(N x){node->apply(x);} M value(){return rev?node->lav:node->val;} }; using Ep=Elem*; Ep meld(Ep s,Ep t){ return new Elem(meld(s->node,t->node),0); } pair<Ep,Ep> split(Ep t,int k){ if(t->rev)k=sz(t->node)-k; auto [L,R]=split(t->node,k); if(t->rev)swap(L,R); auto LE=new Elem(L,t->rev); auto RE=new Elem(R,t->rev); return {LE,RE}; } const int n; SegmentTree<M,N,f,g,m1> seg; set<int> Ls; vector<Ep> Es; void split(int k){ if(k>=n)return; int pos=*(--Ls.upper_bound(k)); if(pos==k)return; auto [L,R]=split(Es[pos],k-pos); Es[pos]=L,Es[k]=R; seg.set(pos,Es[pos]->value()); seg.set(k,Es[k]->value()); Ls.insert(k); } }; /** * @brief Sortable Segment Tree */