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

· · 题解

树状数组+二分：

这题，既然线段树能A掉，树状数组又怎么能落后呢？
考虑裸的树状数组：
对于操作1：直接add(x,1)
对于操作2：直接add(x,-1)
对于操作3：直接query(x)查找x前面有多少个数
对于操作4：二分一个值，在检验这个值是否可行
对于操作5和6：先找到x的排名，再分别查找排名为x-1和x+1的数

至此问题不就完美解决吗？

还是贴下代码吧
#include<cstdio>
#include<algorithm>
#include<cstring>
#define low(x) (x&(-x))
using namespace std;
const int ep=1e7+1;
const int MX=2e7+1;
int t[20000005];
int n,I;
void add(int x,int val){for(I=x;I<=MX;I+=low(I))t[I]+=val;}
int q(int x){int an=0;for(I=x;I;I-=low(I))an+=t[I];return an;}
int rank(int x)
{
    int l=1,r=MX,mid;
    int tmp;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(q(mid)<x)l=mid+1,tmp=mid;
        else r=mid-1;
    }return tmp-ep+1;
}
int main()
{
    scanf("%d",&n);
    int i,opt,x;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&opt,&x);
        if(opt==1)add(x+ep,1);
        else if(opt==2)add(x+ep,-1);
        else if(opt==3)printf("%d\n",q(x+ep-1)+1);
        else if(opt==4)printf("%d\n",rank(x));
        else if(opt==5)printf("%d\n",rank(q(x+ep-1)));
        else printf("%d\n",rank(q(x+ep)+1));
    }return 0;
}