平衡树维护序列的板子题。
用\(fhqTreap\)
考虑在分裂时,用子树大小来分,因为我们相当要分裂出三个区间\([1,l - 1][l,r][r + 1,n]\)这个区间是按\(k_{th}\)分的,这个\(k_{th}\)指的的坐标序列。
文艺平衡树
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
#define M 10000010
ll ch[M][2],val[M],siz[M],lazy[M],key[M];
inline ll randdom(){return rand() << 15 | rand();}
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define v(x) val[x]
#define s(x) siz[x]
#define la(x) lazy[x]
#define c(x) key[x]
ll cnt;
inline ll newcode(ll x){
v(++cnt) = x;
s(cnt) = 1;
la(cnt) = 0;
c(cnt) = randdom();
// std::cout<<randdom()<<std::endl;
ls(cnt) = rs(cnt) = 0;
return cnt;
}
inline void up(ll x){
s(x) = s(ls(x)) + s(rs(x)) + 1;
}
inline void down(ll x){
std::swap(ls(x),rs(x));
la(x) = 0;
if(ls(x))
la(ls(x)) ^= 1;
if(rs(x))
la(rs(x)) ^= 1;
}
inline void split(ll now,ll k,ll &x,ll &y){
if(!now){
x = y = 0;
// std::cout<<now<<" "<<k<<" "<<ls(now)<<" "<<rs(now)<<" "<<x<<" "<<y<<std::endl;
return ;
}
if(la(now))
down(now);
if(s(ls(now)) < k){
x = now;
split(rs(now),k - s(ls(now)) - 1,rs(now),y);
}else{
y = now;
split(ls(now),k,x,ls(now));
}
// std::cout<<now<<" "<<k<<" "<<ls(now)<<" "<<rs(now)<<" "<<x<<" "<<y<<std::endl;
up(now);
}
inline ll merge(ll x,ll y){//涉及到子树递归操作就要记得down
// std::cout<<x<<" "<<y<<""<<std::endl;
if(!x || !y)
return x + y;
if(c(x) < c(y)){
if(la(x))
down(x);
rs(x) = merge(rs(x),y);
up(x);
return x;
}else{
if(la(y))
down(y);
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
inline void print(ll now){
if(!now)return;
if(la(now))
down(now);
print(ls(now));
std::cout<<v(now)<<" ";
print(rs(now));
return ;
}
ll n,m,root;
int main(){
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= n;++i)
root = merge(root,newcode(i));
for(int i = 1;i <= m;++i){
ll l,r,x,y,z;//[1,l-1][l,r][r + 1,n]
scanf("%lld%lld",&l,&r);
split(root,l - 1,x,y);
// std::cout<<x<<" "<<y<<std::endl;
split(y,r - l + 1,y,z);
la(y) ^= 1;
// std::cout<<x<<" "<<y<<" "<<z<<std::endl;
root = merge(x,merge(y,z));
// std::cout<<root<<std::endl;
}
print(root);
return 0;
}