fhq-treap 题解

思路

C 操作

C 操作是比较简单的，把区间 Split 出来输出 size 即可。

F 操作

直接拆开后区间加在合并显然是不可取的，因为两个区间的最大最小值可能会有冲突。

例如 $3,3,4,4$ 整体加一后和 $4,4$ 合并，变成 $4,4,5,5,4,4$ 。

记前面区间为 $q1$，后面区间为 $q2$。我们考虑将 $q1$ 再次拆分，记 $q2$ 的最小值为 $m$，将 $q1$ 拆分为所有元素 $<m$ 的区间 $q3$ 与所有元素 $=m$ 的区间 $q4$，将 $q3$ 接到 $q2$ 之前，$q4$ 接在 $q2$ 中所有 $m$ 之后即可，这样整体加一后序列还是有序的。

AC CODE

#include <bits/stdc++.h>
#include <random>
#define ls tree[i].lson
#define rs tree[i].rson
using namespace std;
inline int read(){
	int ans=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		ans=(ans<<1)+(ans<<3)+ch-'0';
		ch=getchar();
	}
	return w*ans;
}
random_device R;
mt19937 G(R());
int rd(int l,int r){
	return uniform_int_distribution<int>(l,r)(G);
}
struct tree{
	int lson;
	int rson;
	int val;
	int sz;
	int pri;
	int lazy;
}tree[1000005];
int Root;
int tim;
int n,m;
void pushup(int i){
	tree[i].sz=tree[ls].sz+tree[rs].sz+1;
}
void new_node(int &x,int val){
	x=++tim;
	tree[x]={0,0,val,1,rd(1,1e9),0};
}
void pushdown(int i){
	if(tree[i].lazy){
		if(ls){
			tree[ls].lazy+=tree[i].lazy;
			tree[ls].val+=tree[i].lazy;
		}
		if(rs){
			tree[rs].lazy+=tree[i].lazy;
			tree[rs].val+=tree[i].lazy;
		}
		tree[i].lazy=0;
	}
}
void split_val(int i,int &l,int &r,int val){
	if(!i){
		l=r=0;
		return;
	}
	pushdown(i);
	if(tree[i].val<=val){
		l=i;
		split_val(tree[i].rson,tree[l].rson,r,val);
	}
	else{
		r=i;
		split_val(tree[i].lson,l,tree[r].lson,val);
	}
	pushup(i); 
}
void split_sz(int i,int &l,int &r,int sz){
	if(!i){
		l=r=0;
		return;
	}
	pushdown(i);
	if(tree[ls].sz+1<=sz){
		l=i;
		split_sz(tree[i].rson,tree[l].rson,r,sz-tree[ls].sz-1);
	}
	else{
		r=i;
		split_sz(tree[i].lson,l,tree[r].lson,sz);
	}
	pushup(i); 
}
void merge(int &i,int l,int r){
	if(!l||!r){
		i=l|r;
		return;
	}
	pushdown(i);
	pushdown(l);
	pushdown(r);
	if(tree[l].pri>tree[r].pri){
		i=l;
		merge(tree[i].rson,tree[l].rson,r);
	}
	else{
		i=r;
		merge(tree[i].lson,l,tree[r].lson);
	}
	pushup(i);
}
int getmin(int i){
	pushdown(i);
	if(!tree[i].lson)return tree[i].val;
	return getmin(tree[i].lson);
}
void insert(int val){
	int root1,root2,root3,root4;
	split_val(Root,root1,root2,val);
	new_node(root3,val);
	merge(root4,root1,root3);
	merge(Root,root4,root2);
}
void F(int c,int h){
	int root1,root2,root3,root4,root5,root6,root7,root8;
	split_val(Root,root1,root2,h-1);
	split_sz(root2,root3,root4,c);
	//root1 --> root3 --> root4
	int minn=getmin(root4);
	split_val(root3,root5,root6,minn-1);
	split_val(root4,root7,root8,minn);
	tree[root5].lazy++;
	tree[root5].val++;
	tree[root6].lazy++;
	tree[root6].val++;
	merge(root3,root5,root7);
	merge(root3,root3,root6);
	merge(root2,root3,root8);
	merge(Root,root1,root2);
}
void C(int l,int r){
	int root1,root2,root3,root4;
	split_val(Root,root1,root2,l-1);
	split_val(root2,root3,root4,r);
	printf("%d\n",tree[root3].sz);
	merge(root2,root3,root4);
	merge(Root,root1,root2);
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		int x=read();
		insert(x);
	}
	while(m--){
		char ch=getchar();
		if(ch=='F'){
			int c=read(),h=read();
			F(c,h);
		}else{
			int l=read(),r=read();
			C(l,r);
		}
	}
}