【题解】Luogu 3871【[TJOI2010]中位数】

背景

这题也是很烦,因为有偶数个操作,以前的对顶堆都是对于单数个而写的,于是就用了PBDS红黑树水过了。

代码

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<algorithm>
#include<functional>
#include<cstdio>
typedef long long int64;
using __gnu_pbds::tree;using __gnu_pbds::null_type;using __gnu_pbds::rb_tree_tag;using __gnu_pbds::tree_order_statistics_node_update;
using std::string;using std::less;
tree<int64,null_type,less<int64>,rb_tree_tag,tree_order_statistics_node_update> OST;

int main(){
    int64 n,m,i,delta;scanf("%lld",&n);
    char op[6];
    for(i = 0;i < n;i++) scanf("%lld",&delta),OST.insert((delta << 20) + i);
    scanf("%lld",&m);
    while(m--){
        scanf("%s",op);
        if(op[0] == 'm'){
            if(n % 2 == 0) delta = *OST.find_by_order(n / 2 - 1);
            else delta = *OST.find_by_order(n / 2);
            printf("%lld\n",delta >> 20);
        }
        else{
            i++,n++;scanf("%lld",&delta);
            OST.insert((delta << 20) + i);
        }
    }
    return 0;
}