49pts

如果被卡了的话想知道原理（

而且平衡树常数是不是很大（

求助（T 操作用 exgcd，没啥区别）：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll mod=317847191;
ll n,k,x,root,cnt,nowx=1;
map<ll,bool> f;
struct treap{
	ll l,r,cnt=0;
	ll x,pri,size;
}a[N];
ll new_node(ll x){
	a[++cnt].x=x;
	a[cnt].pri=rand();
	a[cnt].cnt++;
	nowx=(nowx%mod*x%mod)%mod;
	return cnt;
}
void lturn(ll &now){
	ll tmp=a[now].r;
	a[now].r=a[tmp].l;
	a[tmp].l=now;
	now=tmp;
}
void rturn(ll &now){
	ll tmp=a[now].l;
	a[now].l=a[tmp].r;
	a[tmp].r=now;
	now=tmp;
}
void insert(ll &now,ll x){
    if(!now){
        now=new_node(x);  
        return;
    }
    if(x==a[now].x) a[now].cnt++,nowx=(nowx%mod*x%mod)%mod;      
    else{
        if(x<a[now].x){                         
            insert(a[now].l,x);
            if(a[now].pri<a[a[now].l].pri&&a[now].l) rturn(now);   
        }else{
            insert(a[now].r,x);                          
            if(a[now].pri<a[a[now].r].pri&&a[now].r) lturn(now);   
        }
    }     
}
ll Pow(ll a,ll k){
	ll ans=1;
	while(k){
		if(k&1) ans=(ans%mod*a%mod)%mod;
		a=(a%mod*a%mod)%mod;
		k>>=1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &c,ll &k){
	if(!b){
		c=1,k=0;
		return a;
	}
	ll p=exgcd(b,a%b,c,k);
	ll q=c;
	c=k,k=q-a/b*k;
	return p;
}
void for_ans(ll p,ll mod,ll nowx,ll &c,ll &k){
	ll d=exgcd(p,mod,c,k);
	ll u=nowx/d;
	c=(c%mod*u%mod)%mod;
	k=(k%mod*u%mod)%mod;
	c=(c+mod)%mod;
}
void real_delete(ll &now){
	ll c=0,k=0;
	ll p=Pow(a[now].x,a[now].cnt);
	for_ans(p,mod,nowx,c,k);
	nowx=c,a[now].cnt=0,now=0;
}
void remove(ll &now,ll x){
    if(!now) return;   
    if(x==a[now].x){
        if(a[now].l||a[now].r){                                
            if(!a[now].r||a[a[now].l].pri>a[a[now].r].pri){     
                rturn(now);                               
                remove(a[now].r,x);
            }else{
                lturn(now);                 
                remove(a[now].l,x);
            }
        }else real_delete(now);                                     
        return;
    }
    if(x<a[now].x) remove(a[now].l,x);       
    else remove(a[now].r,x);                                    
}
ll find_max(ll now){
	if(a[now].r) return find_max(a[now].r);
	else return a[now].x;
}
ll find_min(ll now){
	if(a[now].l) return find_min(a[now].l);
	else return a[now].x;
}
int main(){
	scanf("%lld %lld",&n,&k);
	for(register int i=1;i<=n;i++){
		scanf("%lld",&x);
		insert(root,x);
	}
	for(register int i=1;i<=k;i++){
		char op=getchar();
		while(op>'Z'||op<'A') op=getchar();
		if(op=='M'){
			ll maxn=find_max(root);
			ll minn=find_min(root);
			printf("%lld\n",Pow(maxn,minn));
		}
		if(op=='D'){
			ll x;
			scanf("%lld",&x);
			if(f[x]) continue;
			f[x]=true;
			remove(root,x);
		}
		if(op=='B') printf("%lld\n",find_max(root));
		if(op=='S') printf("%lld\n",find_min(root));
		if(op=='T') printf("%lld\n",nowx);
		//M D B S T 可见出题人多么讨厌二叉搜索树（ 
	}
}