BZOJ 1208 [HNOI2004]宠物收养所

题目大意

请你维护一个数据结构，支持：插入一个元素，查询和某个点权值最接近的点，删除某个点。

这道题需要维护的是集合所以很自然地想到可以用权值线段树维护。建立权值线段树，按着题意进行插入删除操作就可以了。注意因为维护总区间的R=2147483647，所以如果暴力求mid会打出GG，维护的时候记得中间mid一定用ll表示，至于传参还是使用int就可以了qwq

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 2147483647
int n,ls[4000010],rs[4000010],siz[4000010],inx,ans,root,tot,mode,status;
void add(int &pos,int l,unsigned int r,int tx)
{
    if(!pos) pos=++tot;
    siz[pos]++;
    if(l==r) return;
    unsigned int mid=(l+r)>>1;
    if(tx<=mid) add(ls[pos],l,mid,tx);
    else add(rs[pos],mid+1,r,tx);
}
int getrank(int pos,int l,int r,int tx)
{
    if(!pos) return 0;
    if(l==r) return siz[pos];
    long long mid=((long long)l+r)>>1;
    if(tx<=mid) return getrank(ls[pos],l,mid,tx);
    else return getrank(rs[pos],mid+1,r,tx)+siz[ls[pos]];
}
int getnum(int pos,int l,int r,int tx)
{
    if(l==r) return l;
    long long mid=((long long)l+r)>>1;
    if(tx<=siz[ls[pos]]) return getnum(ls[pos],l,mid,tx);
    else return getnum(rs[pos],mid+1,r,tx-siz[ls[pos]]);
}
void del(int pos,int l,int r,int tx)
{
    siz[pos]--;
    if(l==r) return;
    long long mid=((long long)l+r)>>1;
    if(tx<=mid) del(ls[pos],l,mid,tx);
    else del(rs[pos],mid+1,r,tx);
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&mode,&inx);
        if(siz[root]==0){status=mode;add(root,1,maxN,inx);}
        else
        {
            if(mode!=status)
            {
                int tx=getrank(root,1,maxN,inx),ty=0x7f7f7f7f;
                if(tx<siz[root]) ty=getnum(root,1,maxN,tx+1);
                if(tx) tx=getnum(1,1,maxN,tx);
                else tx=ty;
                if(ty==0x7f7f7f7f) del(root,1,maxN,tx),ans=(ans+abs(inx-tx))%1000000;
                else
                {
                    if(abs(inx-tx)==abs(inx-ty))
                    {
                        del(root,1,maxN,min(tx,ty));
                        ans=(ans+abs(inx-ty))%1000000;
                        continue;
                    }
                    if(abs(inx-tx)>abs(inx-ty))
                    {
                        del(root,1,maxN,ty);
                        ans=(ans+abs(inx-ty))%1000000;
                        continue;
                    }
                    if(abs(inx-tx)<abs(inx-ty))
                    {
                        del(root,1,maxN,tx);
                        ans=(ans+abs(inx-tx))%1000000;
                        continue;
                    }
                }
            }
            else add(root,1,maxN,inx);
        }
    }
    printf("%d\n",ans);
    return 0;
}