#pragma once
#include"../basic/template.hpp"template<classT>classRBST{classNode{public:Node*left=nullptr,*right=nullptr;Tvalue;size_tsize;};Node*root=nullptr;RBST(Node*r):root(r){}staticulintengine(){staticulintcur=std::clock();cur^=cur<<13;cur^=cur>>17;cur^=cur<<5;returncur;}staticsize_tsize(Node*trg){returntrg?trg->size:0;}staticNode*apply(Node*trg){trg->size=size(trg->left)+size(trg->right)+1;returntrg;}staticNode*merge(Node*left,Node*right){if(!left)returnright;if(!right)returnleft;if(size_t(engine()%(size(left)+size(right)))<size(left)){left->right=merge(left->right,right);returnapply(left);}else{right->left=merge(left,right->left);returnapply(right);}}staticstd::pair<Node*,Node*>split(Node*trg,intpos){if(!trg)return{nullptr,nullptr};if(pos<=size(trg->left)){autotmp=split(trg->left,pos);trg->left=tmp.second;return{tmp.first,apply(trg)};}else{autotmp=split(trg->right,pos-size(trg->left)-1);trg->right=tmp.first;return{apply(trg),tmp.second};}}staticNode*insert(Node*node,intidx,constT&val){autotmp=split(node,idx);returnmerge(merge(tmp.first,newNode{nullptr,nullptr,val,1}),tmp.second);}staticNode*erase(Node*node,intidx){autoleft=split(node,idx);autoright=split(left.second,1);deleteright.first;returnmerge(left.first,right.second);}staticNode*build(conststd::vector<T>&data,intl,intr){if(r==-1)r=data.size();if(data.empty()||l>=r)returnnullptr;intidx=engine()%(r-l)+l;returnapply(newNode{build(data,l,idx),build(data,idx+1,r),data[idx],1});}voidclear(Node*trg){if(!trg)return;clear(trg->left);clear(trg->right);deletetrg;}public:RBST(){}RBST(conststd::vector<T>&data){this->build(data);}RBSTmerge(constRBST&trg){returnRBST(merge(root,trg.root));}std::pair<RBST,RBST>split(intpos){autotmp=split(root,pos);return{RBST(tmp.first),RBST(tmp.second)};}T&find(intidx)const{Node*cur=root;intcnt=0;while(true){if(cnt+size(cur->left)==idx)returncur->value;elseif(cnt+size(cur->left)>idx)cur=cur->left;elsecnt+=size(cur->left)+1,cur=cur->right;}}T&operator[](intidx)const{returnfind(idx);}voidinsert(intidx,constT&val){root=insert(root,idx,val);}voiderase(intidx){root=erase(root,idx);}intupper_bound(intval)const{Node*cur=root;intres=0,cnt=0;while(cur){if(cur->value<=val)cnt+=size(cur->left)+1,cur=cur->right;else{res+=cnt;cnt=0;cur=cur->left;}}returnres+cnt;}intlower_bound(intval)const{Node*cur=root;intres=0,cnt=0;while(cur){if(cur->value<val)cnt+=size(cur->left)+1,cur=cur->right;else{res+=cnt;cnt=0;cur=cur->left;}}returnres+cnt;}voidbuild(conststd::vector<T>&data){root=build(data,0,-1);}voidclear(){clear(root);root=nullptr;}intsize()const{returnempty()?0:root->size;}boolempty()const{return!root;}};/**
* @title Randomized Binary Search Tree
*/