P3369普通平衡树


树状数组实现平衡树

有关平衡树的问题很多时候其实是可以用树状数组或是set来处理的,但似乎题解很少有这方面的说明赶紧水一发

本题值域范围不大,所以可以之间在线做,但一般开到$10^9$,这时候就需要离散化三连sort,unique,lower_bound,在离散化之后树状数组用来维护值域

首先对于操作1,直接在x对应的位置+1就好了,操作2同理

操作3只要查询x-1的前缀和就是比x的小的所有的数,+1就是排名了

操作4就是找到前缀和中第一个大于等于x的对应的数,因为前缀和其实就是排名

操作5和6同理,5中比如比x小的有k个数,我只要正好找到前缀和中第一个大于等于k对应的数就好了,需要注意的是两个操作的实现有一些不同

if(p[i]==5) printf("%d\n",query(sum(hash(a[i])-1)));
if(p[i]==6) printf("%d\n",query(sum(hash(a[i]))+1));

为什么查询前驱
从$sum(i-1)$里找而后继要从$sum(i)+1$而不是$sum(i+1)$里找呢,这是因为我们为了离散化方便把查询排名的x也插了进去,这个地方可能是没有数的,$sum(i+1)$就和$sum(i)$一样了,所以这样处理
而如何查询第一个前缀和大于等于x对应的数呢,这里有两种方法,一种就是二分,还有一种就是通过树状数组的性质来处理,二分似乎之前有一篇题解提到过,这里介绍第二种方法

首先树状数组其实是一颗二叉树,让我们看这幅图

图片来源网络

我们发现二的幂次方维护的值从开头开始的,假设我们现在在8这个点,维护的是8的前缀和,但这个值已经比k大了,不满足最小,所以我们跳到4,其实就相当于往左儿子走,假如5是符合要求的,那我们从4跳到6(+$2^1$)发现不可以,再跳到5($+2^0$)发现可以,之后返回,所以时间复杂度是和$logn$有关的,总以通过

接下来是代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,q[maxn],a[maxn],p[maxn],tot=0,c[maxn];
int hash(int x){return lower_bound(q+1,q+1+tot,x)-q;}
int lowbit(int x){return x&-x;}
void add(int x,int p)
{
    while(x<=tot)
    {
        c[x]+=p;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int query(int x)
{
    int t=0;
    for(int i=19;i>=0;i--)
    {
        t+=1<<i;
        if(t>tot||c[t]>=x) t-=1<<i;
        else x-=c[t];
    }
    return q[t+1];
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        p[i]=read(),a[i]=read();
        if(p[i]!=4) q[++tot]=a[i];
    }
    //hash
    sort(q+1,q+1+tot);
    tot=unique(q+1,q+1+tot)-(1+q);
    for(int i=1;i<=n;i++)
    {
        if(p[i]==1) add(hash(a[i]),1);
        if(p[i]==2) add(hash(a[i]),-1);
        if(p[i]==3) printf("%d\n",sum(hash(a[i])-1)+1);
        if(p[i]==4) printf("%d\n",query(a[i]));
        if(p[i]==5) printf("%d\n",query(sum(hash(a[i])-1)));
        if(p[i]==6) printf("%d\n",query(sum(hash(a[i]))+1));
    }
    return 0;
} 

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P2420让我们异或吧 P2420让我们异或吧
其实这道题并不需要用LCA,这是对经典模型:树上两点之间路径距离的改编,因为异或逆运算就是他本身,所以LCA(u,v)就被抵消了,只需要dis[u]+dis[v]就可以了,然后建个图,跑个dfs就出来了 <!–more> #in
2019-07-05
下一篇 
P1631序列合并 P1631序列合并
首先对于两个序列$a,b$最小的肯定是$a_1+b_1$,而次小的就有两种可能$min(a_1+b_2,a_2+b_1)$,假如现在次小是$a_1+b_2$,那么最小的比他大的数就是$min(a_1+b_3,a_2+b_2)$,再与之前的$
2019-07-05
  目录