插入标记回收算法

\(f_Rf_{R-1}\dots f_{l+1}(f_l(x))=f_l\circ f_{l+1}\dots \circ f_{r-1} \circ f_r\)

• 插入：如果存在以 \(i\) 位置为左端点的区间询问，则需要将该询问的初值插入集合 \(S\) 中。

• 标记：扫描线每次从 \(i\) 扫到 \(i+1\) 时对 \(S\) 进行全局修改，通常通过打标记实现。

• 回收：如果存在以 i 位置为右端点的区间询问，则需要查询该询问目前的答案

template<typename T>
struct ptr{static T data[maxn];static int tot;int p;ptr<T>& alloc(){return p=++tot,*this;}T* operator->(){return &data[p];}explicit operator bool(){return p;}friend bool operator==(ptr<T> x,ptr<T> y){return x.p==y.p;}
};template<typename T>T ptr<T>::data[maxn];
template<typename T>int ptr<T>::tot;#define self ptr<Node>{int(this-ptr<Node>::data)}mt19937 gen(4);struct Node{ptr<Node> ls,rs,fa;int val,rk;int valadd;void tagadd(int want){val+=want,valadd+=want;}void push_down(){if(valadd) ls->tagadd(valadd),rs->tagadd(valadd),valadd=0;}pair<ptr<Node>,ptr<Node>> split(int x){if(!self) return {};push_down();if(val<=x){auto tmp=rs->split(x);return rs=tmp.x,tmp.x->fa=self,tmp.y->fa={},make_pair(self,tmp.y);}else{auto tmp=ls->split(x);return ls=tmp.y,tmp.y->fa=self,tmp.x->fa={},make_pair(tmp.x,self);}}int getfst(){ptr<Node> x=self;while(x->ls) x->push_down(),x=x->ls;return x->val;}friend ptr<Node> merge(ptr<Node> x,ptr<Node> y){if(!x) return y;if(!y) return x;if(x->rk<y->rk) return x->push_down(),x->rs=merge(x->rs,y),x->rs->fa=x,x;else return y->push_down(),y->ls=merge(x,y->ls),y->ls->fa=y,y;}friend ptr<Node> join(ptr<Node> x,ptr<Node> y){ptr<Node> ans{};while(x){auto tmp=x->split(y->getfst());ans=merge(ans,tmp.x),x=tmp.y;swap(x,y);}return merge(ans,y);}void load(){static ptr<Node> stk[maxn];int tot=0;ptr<Node> x=self;while(x->fa) x=x->fa,stk[++tot]=x;while(tot) stk[tot--]->push_down();}void check(){if(ls) assert(ls->fa==self),ls->check();if(rs) assert(rs->fa==self),rs->check();}void dbg(string s=""){if(!self) return;cerr<<s<<"id:"<<self.p<<",val:"<<val<<endl;push_down();ls->dbg(s+"  "),rs->dbg(s+"  ");}
};

QOJ8672