平衡树
constexpr int block=500,inf=2e9;
struct BlockList{vector<vector<int>> b;void split(size_t idx){if(b[idx].size()>2*block){size_t mid=b[idx].size()/2;vector<int> temp;temp.insert(temp.begin(),b[idx].begin()+mid,b[idx].end());b[idx].resize(mid);b.insert(b.begin()+idx+1,temp);}}void merge(size_t idx){if(b[idx].empty()&&b.size()>1){b.erase(b.begin()+idx);return;}if(idx+1<b.size()&&b[idx].size()+b[idx+1].size()<block*2){b[idx].insert(b[idx].end(),b[idx+1].begin(),b[idx+1].end());b.erase(b.begin()+idx+1);}}BlockList(){b.push_back({});}void insert(int x){for(size_t i=0;i<b.size();i++)if(!b[i].empty()&&x<b[i].back()){auto it=lower_bound(b[i].begin(),b[i].end(),x);b[i].insert(it,x);split(i);return;}if(b.back().size()<2*block) b.back().push_back(x);else b.push_back({x});}void erase(int x){for(size_t i=0;i<b.size();i++)if(x<=b[i].back()){auto it=lower_bound(b[i].begin(),b[i].end(),x);if(*it!=x) return;b[i].erase(it);merge(i);return;}}size_t rnk(int x){size_t cnt=0;for(size_t i=0;i<b.size();i++){if(b[i].empty()) continue;if(b[i].back()<x) cnt+=b[i].size();else{auto it=lower_bound(b[i].begin(),b[i].end(),x);cnt+=it-b[i].begin();return cnt+1;}}return cnt+1;}size_t kth(size_t x){size_t cnt=0;for(size_t i=0;i<b.size();i++){if(cnt+b[i].size()>=x)return b[i][x-cnt-1];cnt+=b[i].size();}return -1;}int pre(int x){int res=-inf;for(size_t i=0;i<b.size();i++){if(b[i].empty()) continue;if(b[i].back()<x) res=b[i].back();else{auto it=lower_bound(b[i].begin(),b[i].end(),x);if(it!=b[i].begin())res=*--it;return res;}}return res;}int nxt(int x){int res=inf;for(size_t i=0;i<b.size();i++){auto it=upper_bound(b[i].begin(),b[i].end(),x);if(it!=b[i].end()){res=*it;return res;}}return res;}
}rope;
文艺平衡树
constexpr int block=350;
struct BlockList{vector<vector<int>> b;vector<char> tag;BlockList(){b.push_back({});tag.push_back(0);}inline void push_down(size_t idx){if(!tag[idx]) return;reverse(b[idx].begin(),b[idx].end());tag[idx]=0;}void merge(size_t idx){if(idx+1>=b.size()) return;if(b[idx].size()+b[idx+1].size()<block*2){push_down(idx),push_down(idx+1);b[idx].insert(b[idx].end(),b[idx+1].begin(),b[idx+1].end());b.erase(b.begin()+idx+1);tag.erase(tag.begin()+idx+1);}}size_t split_pos(size_t pos){size_t cnt=0;for(size_t i=0;i<b.size();i++){if(cnt+b[i].size()>pos){push_down(i);size_t idx=pos-cnt;if(idx==0) return i;vector<int> temp;temp.assign(b[i].begin()+idx,b[i].end());b[i].resize(idx);b.insert(b.begin()+i+1,temp);tag.insert(tag.begin()+i+1,0);return i+1;}cnt+=b[i].size();if(cnt==pos) return i+1;}return b.size();}inline size_t bel(size_t x){size_t cnt=0;for(size_t i=0;i<b.size();i++)if(cnt+b[i].size()>=x) return i;else cnt+=b[i].size();return -1;}void insert(int x){if(b.back().size()<block) b.back().push_back(x);else b.push_back({x}),tag.push_back(0);}void rev(int l,int r){size_t x=split_pos(l),y=split_pos(r+1);reverse(b.begin()+x,b.begin()+y);reverse(tag.begin()+x,tag.begin()+y);for(size_t i=x;i<y;i++) tag[i]^=1;if(y>0) merge(y-1);if(x>0) merge(x-1);}void print(){for(size_t i=0;i<b.size();i++){push_down(i);for(int x:b[i]) cout<<x<<' ';}}
}rope;
