最后一个点TLE球调

回复帖子

@fzj2007 2021-04-11 13:59 回复

RT....貌似没有找到明显错误。

用的Treap。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
template<typename T>inline void read(T &x){//优化
    x=0;
    char ch=getchar();
    bool fl=0;
    while(ch<'0'||ch>'9') fl=(fl||ch=='-'),ch=getchar();
    while(ch<='9'&&ch>='0') x=x*10+(ch^'0'),ch=getchar();
    x=fl?-x:x;
}
template<typename T>void prt(T x){
    if(x>9) prt(x/10);
    putchar(x%10+'0');
}
template<typename T>inline void put(char ch,T x){
    if(x<0) putchar('-'),x=-x;
    prt(x);
    putchar(ch);
}
inline char getc(){
    char ch=getchar();
    while(ch!='a'&&ch!='m') ch=getchar();
    return ch;
}
#define N 150005
int root,cnt,n,m;
struct node{//lson左儿子,rson右儿子,val权值,num当前权值个数,siz子树大小,key维护堆
    int lson,rson,val,num,siz,key;
}t[N];
#define lc(X) t[X].lson
#define rc(X) t[X].rson
namespace Treap{
    inline void push_up(int x){//更新
        t[x].siz=t[lc(x)].siz+t[rc(x)].siz+t[x].num;
    }
    inline int make_node(int val){//新建结点
        t[++cnt].key=rand();
        t[cnt].num=t[cnt].siz=1;
        t[cnt].val=val;
        return cnt;
    }
    inline void lrotate(int &x){//旋转
        int k=rc(x);
        rc(x)=lc(k);
        lc(k)=x;
        t[k].siz=t[x].siz;
        push_up(x);
        x=k;
    }
    inline void rrotate(int &x){
        int k=lc(x);
        lc(x)=rc(k);
        rc(k)=x;
        t[k].siz=t[x].siz;
        push_up(x);
        x=k;
    } 
    void insert(int &x,int val){//插入
        if(!x) return x=make_node(val),void();
        t[x].siz++;
        if(t[x].val==val) t[x].num++;//直接维护
        else if(t[x].val>val){
            insert(lc(x),val);
            if(t[x].key>t[lc(x)].key) rrotate(x);//维护堆
        }else{
            insert(rc(x),val);
            if(t[x].key<t[rc(x)].key) lrotate(x);//维护堆
        }
    }
    int qnum(int x,int k){//x表示当前结点,k表示查询子树中第k小
        if(!x) return 0;//虽然没有必要...
        if(t[lc(x)].siz>=k) return qnum(lc(x),k);//在左子树
        if(t[x].num+t[lc(x)].siz<k) return qnum(rc(x),k-t[x].num-t[lc(x)].siz);//在又子树
        return t[x].val;//直接返回
    }
}
using namespace Treap;
int main(){
    srand(time(NULL));
    read(n);
    for(int i=1,x;i<=n;i++) read(x),insert(root,x);//插进去
    read(m);
    for(int i=1,x;i<=m;i++)
        if(getc()=='a') read(x),insert(root,x);//如果add就插进去
        else put('\n',qnum(root,(t[root].siz+1)>>1));//查询

    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。