题解 P3369 【【模板】普通平衡树】

· · 题解

平衡树的模板题怎么可以用平衡树写呢？

本篇题解使用动态开点权值线段树，没有使用任何STL和离线等操作来维护

不会动态开点权值线段树的同学先去学习

  1. 因为值域范围是 [-1e7,1e7]，操作个数是 1e5 ，所以加入 1 个数最多会开 log_22e7 大约 25 个节点，所以线段树节点信息数组大小应开到 25 * 100000 = 2500000，这里保险开了 3000000=3*10^6

操作1和2这里不讲，too simple

  1. 操作 4 ：查询当前节点内第 k 小值时，如果 k 小于等于左子树内数的个数，那么说明第 k 小数在左子树内，直接进去；否则，这个数肯定在右子树内了，这时候我们只要查询右子树内的第 k - 左子树内数的个数 小值就行了

  2. 操作 3 ：直接查询 [-1e7,x-1] 范围内有多少数，+1 输出就行了

  3. 操作 5 ：我们先查询出 [-1e7,x-1] 范围内有多少数，设为 m，然后用操作 4 查询第 m 小值就行了

  4. 操作 6 ：和操作 5 类似，查询出 [-1e7,x] 范围内有多少数，设为 m ，x 的后继的数当然是第 m+1 小数，所以用操作 4 查询第 m+1 小的数就行了

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
using namespace std;
const int MaxN=100050;
const int MaxTR=3000050;
template <class t> inline void read(t &s)   // 快读
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
#define lson ls[u]
#define rson rs[u]
int val[MaxTR],ls[MaxTR],rs[MaxTR];
int ndcnt=1;
inline void pushup(int u)
{
    val[u]=val[lson]+val[rson];
    return;
}
inline int modify(int &u,int l,int r,int p,int k)
{
    if(!u)
        u=++ndcnt;
    if(l==r)
    {
        val[u]+=k;
        return u;
    }
    reg int mid=(l+r)>>1;
    if(p<=mid)
        modify(lson,l,mid,p,k);
    else
        modify(rson,mid+1,r,p,k);
    pushup(u);
    return u;
}
inline int query(int u,int l,int r,int ql,int qr)
{
    if(!u)
        return 0;
    if(ql<=l&&r<=qr)
        return val[u];
    reg int mid=(l+r)>>1,ans=0;
    if(ql<=mid)
        ans+=query(lson,l,mid,ql,qr);
    if(mid<qr)
        ans+=query(rson,mid+1,r,ql,qr);
    return ans;
}
inline int kth(int u,int l,int r,int k)
{
    if(!u)
        return -1;
    if(l==r)
        return l;
    reg int mid=(l+r)>>1;
    if(k<=val[lson])
        return kth(lson,l,mid,k);
    else
        return kth(rson,mid+1,r,k-val[lson]);
    return -1;
}
signed main(void)
{
    int n;cin>>n;
    reg int opt,x;
    reg int rt=1;
    for(int i=1;i<=n;++i)
    {
        read(opt);read(x);
        if(opt==1)
            modify(rt,-1e7,1e7,x,1);
        else if(opt==2)
            modify(rt,-1e7,1e7,x,-1);
        else if(opt==3)
            printf("%d\n",query(1,-1e7,1e7,-1e7,x-1)+1);
        else if(opt==4)
            printf("%d\n",kth(1,-1e7,1e7,x));
        else if(opt==5)
        {
            reg int t=query(1,-1e7,1e7,-1e7,x-1);
            printf("%d\n",kth(1,-1e7,1e7,t));
        }
        else
        {
            reg int t=query(1,-1e7,1e7,-1e7,x)+1;
            printf("%d\n",kth(1,-1e7,1e7,t));
        }
    }
    return 0;
}