思路

学艺不精,交splay结果WA了,还找不到问题。
所以我还是用了vector写。保持vector是有序的,插入和删除的时候二分,复杂度很优。
记得要清空vector。

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;

int t,n,m,x;
string str;
vector<int>vt;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        vt.clear();
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>x;
            vt.push_back(x);    
        }
        sort(vt.begin(),vt.end());
        for(int i=1;i<=m;i++){
            cin>>str>>x;
            if(str[0]=='q'){
                printf("%d\n",vt[vt.size()-x]);
            }    
            if(str[0]=='i'){
                vt.insert(lower_bound(vt.begin(),vt.end(),x),x);
            }
            if(str[0]=='d') vt.erase(lower_bound(vt.begin(),vt.end(),x));
        }
    }
    return 0;
}