请你维护一些可重集，初始只有一个编号为 \(1\) 的可重集 \(a\)，要支持以下操作：
-
0 p x y：将可重集 \(p\) 中大于等于 \(x\) 且小于等于 \(y\) 的所有元素移动到一个新的可重集中。（其编号从 \(2\) 开始，是上次新建的可重集的编号 \(+1\)。） -
1 p t：将可重集 \(t\) 中的元素全部移动到可重集 \(p\) 中，并清空可重集 \(t\)。（之后的操作中不会出现可重集 \(t\)。） -
2 p x q：在可重集 \(p\) 中加入 \(x\) 个数 \(q\)。 -
3 p x y：询问可重集 \(p\) 中大于等于 \(x\) 且小于等于 \(y\) 的元素的个数。 -
4 p k：询问可重集 \(p\) 中第 \(k\) 小的元素，不存在则输出-1。
考虑用动态开点的权值树维护每个可重集，操作 2，3，4 是容易维护的。
接下来重点看一下 0，1 操作。
1 操作可以用一个线段树合并的方式解决。
一次合并操作会合并两个权值树，产生的权值树可以看作是两个原树对应位置相加而来的。
由于这些权值树维护的值域都是相同的，我们可以用两个指针同时遍历两颗权值树，相加对应节点的值。
设两个指针为 \(p,q\)，要将 \(q\) 遍历的权值树合并到 \(p\) 遍历的权值树上。注意到动态开点的权值树有很多空节点，这时就需要分情况来讨论：
-
若 \(p,q\) 皆非空，在 \(p\) 处加上 \(q\) 处的值，删除 \(q\) 处节点，继续向下递归。
-
若 \(p\) 空，\(q\) 非空，则直接将以 \(q\) 为根的这颗子树接到 \(p\) 处，并返回。
-
若 \(p\) 非空，\(q\) 空，则直接返回。
-
若 \(p,q\) 皆空，直接返回。
代码就是这个样子的：
void merge( int & p , int & q , int l , int r ){
if( ! p ){ p = q; return; }
if( ! q ) return;
if( l == r ){ val( p ) += val( q ) , delet( q ); return; }
int mid = l + r >> 1;
merge( ls( p ) , ls( q ) , l , mid );
merge( rs( p ) , rs( q ) , mid + 1 , r );
delet( q ) , push_up( p );
}
接下来考虑一下这个操作的复杂度。
注意到，若继续向下递归，必然会删除一个节点，于是总递归的次数不会超过总点数。注意这里的总递归次数值得并非一次操作，而是所有的合并操作。
而一次修改操作会新建 \(O(\log n)\) 个节点，\(m\) 次操作，总点数就是 \(O(m\log n)\) 的，所以所有合并操作的总复杂度就是 \(O(m\log n)\) 的。它的复杂度是均摊的。
分裂操作是提取出一颗权值树上的值域区间 \([x,y]\)，对其新建一棵树，于是我们可以和区间操作一样，在原树上定位到对应的 \(\log\) 个区间，并将经过的节点提取出来构成一颗新树，并顺便在原树中将这个值域中的元素减掉。
其实还可以像 fhq-Treap 那个样子按排名分裂，不过上面这个方法更加简单，效率也高一些。
代码的实现：
void split( int & p , int & q , int l , int r , int L , int R ){
if( ! p ) return;
if( L <= l && r <= R ){ q = p , p = 0; return; }
if( ! q ) q = newv();
int mid = l + r >> 1;
if( L <= mid ) split( ls( p ) , ls( q ) , l , mid , L , R );
if( R > mid ) split( rs( p ) , rs( q ) , mid + 1 , r , L , R );
push_up( p ) , push_up( q );
}
容易发现这个操作的复杂度和平凡的区间操作是一样的，为单次 \(O(\log n)\)。
其余三个操作的复杂度都是单次 \(O(\log n)\)。
总时间复杂度 \(O(m\log n)\)。
Code：
# include <cstdio>
# include <iostream>
namespace IO{
inline int read(){
int ret = 0 , ti = 1;
char u = getchar();
while( ! isdigit( u ) ){ if( u == '-' ) ti = -1; u = getchar(); }
while( isdigit( u ) ) ret = ret * 10 + u - '0' , u = getchar();
return ret * ti;
}
}
using namespace std;
typedef long long ll;
const int N = 2e5 + 225;
int n , m;
int a[ N ];
int root[ N ] , nod , cnt;
int recy[ N << 2 ] , tp;
struct Node{ ll v; int lc , rc; }t[ N << 5 ];
# define ls( u ) t[ u ] . lc
# define rs( u ) t[ u ] . rc
# define val( u ) t[ u ] . v
inline int newv(){ return tp ? recy[ tp -- ] : ++ nod; }
inline void delet( int & u ){ ls( u ) = rs( u ) = val( u ) = 0 , recy[ ++ tp ] = u , u = 0; }
inline void push_up( int u ){ val( u ) = val( ls( u ) ) + val( rs( u ) ); }
int build( int & u , int l , int r ){
u = newv();
if( l == r ){ val( u ) = a[ l ]; return u; }
int mid = l + r >> 1;
build( ls( u ) , l , mid );
build( rs( u ) , mid + 1 , r );
push_up( u );
return u;
}
void split( int & p , int & q , int l , int r , int L , int R ){
if( ! p ) return;
if( L <= l && r <= R ){ q = p , p = 0; return; }
if( ! q ) q = newv();
int mid = l + r >> 1;
if( L <= mid ) split( ls( p ) , ls( q ) , l , mid , L , R );
if( R > mid ) split( rs( p ) , rs( q ) , mid + 1 , r , L , R );
push_up( p ) , push_up( q );
}
void merge( int & p , int & q , int l , int r ){
if( ! p ){ p = q; return; }
if( ! q ) return;
if( l == r ){ val( p ) += val( q ) , delet( q ); return; }
int mid = l + r >> 1;
merge( ls( p ) , ls( q ) , l , mid );
merge( rs( p ) , rs( q ) , mid + 1 , r );
delet( q ) , push_up( p );
}
void modify( int & u , int l , int r , int p , int x ){
if( ! u ) u = newv();
if( l == r ){ val( u ) += x; return; }
int mid = l + r >> 1;
if( p <= mid ) modify( ls( u ) , l , mid , p , x );
else modify( rs( u ) , mid + 1 , r , p , x );
push_up( u );
}
ll query1( int u , int l , int r , int L , int R ){
if( ! u ) return 0;
if( L <= l && r <= R ) return val( u );
int mid = l + r >> 1;
ll ret = 0;
if( L <= mid ) ret += query1( ls( u ) , l , mid , L , R );
if( R > mid ) ret += query1( rs( u ) , mid + 1 , r , L , R );
return ret;
}
int kth( int u , int l , int r , int k ){
if( l == r ) return l;
int mid = l + r >> 1;
if( val( ls( u ) ) >= k ) return kth( ls( u ) , l , mid , k );
else return kth( rs( u ) , mid + 1 , r , k - val( ls( u ) ) );
}
void solve(){
for( int i = 1 ; i <= m ; i ++ ){
int op = IO :: read() , p = IO :: read();
if( ! op ){
int l = IO :: read() , r = IO :: read();
split( root[ p ] , root[ ++ cnt ] , 1 , n , l , r );
}
else if( op == 1 ){
int q = IO :: read();
merge( root[ p ] , root[ q ] , 1 , n );
}
else if( op == 2 ){
int c = IO :: read() , x = IO :: read();
modify( root[ p ] , 1 , n , x , c );
}
else if( op == 3 ){
int l = IO :: read() , r = IO :: read();
printf( "%lld\n" , query1( root[ p ] , 1 , n , l , r ) );
}
else{
int k = IO :: read();
if( val( root[ p ] ) < k ) printf( "-1\n" );
else printf( "%d\n" , kth( root[ p ] , 1 , n , k ) );
}
}
}
void input(){
n = IO :: read() , m = IO :: read();
for( int i = 1 ; i <= n ; i ++ ) a[ i ] = IO :: read();
}
int main(){
input();
build( root[ cnt = 1 ] , 1 , n );
solve();
system( "pause" );
return 0;
}