蒟蒻第一篇题解

看到有位%%巨佬%%居然写了红黑树（看不懂）

不过这题可以用线段树k掉

---------------------实现-----------------------

我们把线段树开成一个桶

离线操作

每个节点所代表的区间为区间内数的个数

这样写不仅码量减少了，运行速度也快了不少

1.插入 从根节点到叶子节点，权值+1；

2.删除

         同上，节点权值-1；  
    因此，以上操作可以写成一个函数

inline void add_or_del(int o,int l,int r,int k,int pos)
{
    st[o]+=pos;//加或减
    if(l==r) return;  //到叶子节点
    int mid=(l+r)>>1;     
    if(k<=mid) add_or_del(ls,l,mid,k,pos);   //分别向左右儿子递归
    else add_or_del(rs,mid+1,r,k,pos);
}

非常简单，而且开始都不用建树（桶为空）

3.查询 x 数的排名:

     每次把x与当前区间中点mid比较         

     如果小于等于mid，说明在左区间，向左儿子寻找 

     如果大于mid，说明在右区间  

     这时，它的排名要加上左子树的大小（它比整个左子树的数都大）

     边界，当l==r时（到了叶子），那么return 1；(在[l,r]的区间只有自己，排名第一)

QAQ代码

inline int x_rank_n(int o,int l,int r,int k)
{
    if(l==r) return 1;
    int mid=(l+r)>>1;
    if(k<=mid) return x_rank_n(ls,l,mid,k);
    else return st[ls]+x_rank_n(rs,mid+1,r,k);
}

4.查询排名为x的数

    原理同上，注意在向右儿子找的时候要减去左儿子大小

5.x的前驱

    等于排在   x的排名减一  位置的数

6.x的后继

    等于排在     x+1的排名   位置的数

全部代码如下

#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
#define int long long
#define ls (o<<1)
#define rs (ls|1)
int b[100500];
int a[100500];
int val[100500];
int st[405000];
int n;
int tot;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void put(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        put(x/10);
    putchar(x%10+'0');
}
inline void add_or_del(int o,int l,int r,int k,int pos)
{
    st[o]+=pos;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) add_or_del(ls,l,mid,k,pos);
    else add_or_del(rs,mid+1,r,k,pos);
}
inline int x_rank_n(int o,int l,int r,int k)
{
    if(l==r) return 1;
    int mid=(l+r)>>1;
    if(k<=mid) return x_rank_n(ls,l,mid,k);
    else return st[ls]+x_rank_n(rs,mid+1,r,k);
}
inline int n_rank_x(int o,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(st[ls]>=k) return n_rank_x(ls,l,mid,k);
    else return n_rank_x(rs,mid+1,r,k-st[ls]);
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        val[i]=read();
        a[i]=read();
        if(val[i]!=4)
            b[++tot]=a[i];
    }
    sort(b+1,b+tot+1);
    for(int i=1;i<=n;i++)
    {
        if(val[i]!=4)
            a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }
    for(int i=1;i<=n;i++)
    {
        switch(val[i])
        {
            case 1: add_or_del(1,1,tot,a[i],1);break;
            case 2: add_or_del(1,1,tot,a[i],-1);break;
            case 3: put(x_rank_n(1,1,tot,a[i]));putchar('\n');break;
            case 4: put(b[n_rank_x(1,1,tot,a[i])]);putchar('\n');break;
            case 5: put(b[n_rank_x(1,1,tot,x_rank_n(1,1,tot,a[i])-1)]);putchar('\n');break;
            default: put(b[n_rank_x(1,1,tot,x_rank_n(1,1,tot,a[i]+1))]);putchar('\n');
        }
    }
    return 0;
}

跑了388ms