萌新求助，$\text{FHQ Treap}$ 爆炸

#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
struct FHQTreap
{
	int root,son[MAXN][2],siz[MAXN],key[MAXN],sze;
	ll val[MAXN];
	void Update(int rt)
	{
		siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1;
	}
	int NewNode(ll v)
	{
		siz[++sze]=1;
		val[sze]=v;
		key[sze]=rand();
		return sze;
	}
	int Merge(int x,int y)
	{
//		printf("merge\n");
		if(!x || !y) return x+y;
		if(key[x]<key[y])
		{
			son[x][1]=Merge(son[x][1],y);
			Update(x);
			return x;
		}
		else
		{
			son[y][0]=Merge(x,son[y][0]);
			Update(y);
			return y;
		}
	}
	void Split(int rt,int pos,int &l,int &r)
	{
//		printf("split\n");
		if(!rt) l=r=0;
		else
		{
			if(val[rt]<=pos)
			{
				l=rt;
				Split(son[rt][1],pos,son[rt][1],r);
			}
			else
			{
				r=rt;
				Split(son[rt][0],pos,l,son[rt][0]);
			}
			Update(rt);
		}
	}
	int FindKth(int rt,int pos)
	{
		while(1)
		{
			if(pos<=siz[son[rt][0]]) rt=son[rt][0];
			else if(pos==siz[son[rt][0]]+1) return rt;
			else
			{
				pos-=siz[son[rt][0]]+1;
				rt=son[rt][1];
			}
		}
	}
}T[2];
struct Node
{
	ll l,r,mid;
	friend bool operator < (const Node &x,const Node &y)
	{
		return x.mid<y.mid;
	}
}a[MAXN];
int k,n,tot;
ll pos,ans,Ans;
void Insert(ll val,int id)
{
	int x,y;
	T[id].Split(T[id].root,val,x,y);
	T[id].root=T[id].Merge(T[id].Merge(x,T[id].NewNode(val)),y);
}
void Delete(ll val,int id)
{
	int x,y,z;
	T[id].Split(T[id].root,val,x,z);
	T[id].Split(x,val-1,x,y);
	y=T[id].Merge(T[id].son[y][0],T[id].son[y][1]);
	T[id].root=T[id].Merge(T[id].Merge(x,y),z);
}
ll FindMid(int len,int id)
{
	if(len&1) return T[id].val[T[id].FindKth(T[id].root,len/2+1)];
	else return (T[id].val[T[id].FindKth(T[id].root,len/2)]+T[id].val[T[id].FindKth(T[id].root,len/2+1)])/2;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>k>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		char opt1,opt2;
		cin>>opt1>>x>>opt2>>y;
		if(opt1==opt2) Ans+=abs(x-y);
		else
		{
			a[++tot].mid=x+y>>1;
			a[tot].l=x;
			a[tot].r=y;
		}
	}
	sort(a+1,a+tot+1);
	if(tot&1) pos=a[tot/2+1].mid;
	else pos=(a[tot/2].mid+a[tot/2+1].mid)/2;
	for(int i=1;i<=tot;i++) ans+=abs(a[i].l-pos)+abs(a[i].r-pos)+1;
	if(k==1) return cout<<ans+Ans<<endl,0;
	else if(k==2)
	{
		if(!tot) return cout<<ans+Ans<<endl,0;
		for(int i=1;i<=tot;i++) Insert(a[i].mid,1);
		int L=0,R=tot;
		for(int i=1;i<tot;i++)
		{
			Delete(a[i].mid,1);
			Insert(a[i].mid,0);
			L++;
			R--;
			ll sum=0;
			ll pos1=FindMid(L,0),pos2=FindMid(R,1);
			for(int j=1;j<=i;j++) sum+=abs(a[j].l-pos1)+abs(a[j].r-pos1)+1;
			for(int j=i+1;j<=tot;j++) sum+=abs(a[j].l-pos2)+abs(a[j].r-pos2)+1;
			ans=min(ans,sum);
		}
		cout<<ans+Ans<<endl;
	}
	return 0;
}