96分第20个点什么鬼???

回复帖子

@OYBDOOO 2020-01-14 22:18 回复

96分第20个点什么鬼???

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
const long long vd=(1ll<<40);
int ch[500100*47][2];
int sz[500100*47];
int rt[500100];
map<long long,int>mp;
int n,ttt;
void psup(int o)
{
    sz[o]=sz[ch[o][0]]+sz[ch[o][1]];
}
void modi(int &o,int pre,long long val,int T,int ge)
{
    if(o==0)o=++ttt;
    sz[o]=sz[pre];
    if(T<0)
    {
        sz[o]+=ge;
        return;
    }
    long long wei=((val>>T)&1);
    ch[o][!wei]=ch[pre][!wei];
    modi(ch[o][wei],ch[pre][wei],val,T-1,ge);
    psup(o);
}
long long rnk(int o,long long val)
{
    int j;
    int now=o;
    long long ans=0;
    for(j=45;j>=0;j--)
    {
        if(j==4)
        {
            int my=-1;
        }
        long long wei=((val>>j)&1);
        if(wei==0)
        {
            now=ch[now][0];
        }
        else
        {
            ans=(ans+sz[ch[now][0]]);
            now=ch[now][1];
        }
    }
    return ans;
}
long long kth(int o,long long KQ)
{
    int kkk=KQ;
    long long j;
    int now=o;
    long long ans=0;
    for(j=45;j>=0;j--)
    {
        if(j<=2)
            int my=-1;
        if(sz[ch[now][0]]>=kkk)
        {
            now=ch[now][0];
        }
        else
        {
            kkk-=sz[ch[now][0]];
            ans+=(1ll<<j);
            now=ch[now][1];
        }
    }
    return ans;
}
int main()
{
    freopen("ppp.in","r",stdin);
    freopen("ppp.out","w",stdout);
    int v,opt,i;
    long long x;
    scanf("%d",&n);
    int bb=0;
    int ls=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%lld",&v,&opt,&x);
        if(i==125)
            int my=-1;
        x+=vd;
        if(opt==1)
        {
            if(i==6)
                int my=-1;
            modi(rt[i],rt[v],x,45,1);
            mp[x]++;
        }
        if(opt==2)
        {
            if(mp[x]==0)
            {
                rt[i]=rt[v];
                continue;
            }
            modi(rt[i],rt[v],x,45,-1);
            mp[x]--;
        }
        if(opt==3)
        {
            ls++;
            if(ls==19)
                int my=-1;
            rt[i]=rt[v];
            printf("%lld\n",rnk(rt[i],x)+1);
        }
        if(opt==4)
        {
            ls++;
            if(ls==19)
                int my=-1;
            if(v==6)
                int my=-1;
            x-=vd;
            rt[i]=rt[v];
            printf("%lld\n",kth(rt[i],x)-vd);
        }
        if(opt==5)
        {
            ls++;
            if(ls==19)
                int my=-1;
            rt[i]=rt[v];
            int lsrk=rnk(rt[i],x);
            if(lsrk==0)printf("-2147483647\n");
            else printf("%d\n",kth(rt[i],lsrk)-vd);
        }
        if(opt==6)
        {
            ls++;
            if(ls==19)
                int my=-1;
            rt[i]=rt[v];
            int lkk=rnk(rt[i],x);
            int lsrk=rnk(rt[i],x+1);
            if(lsrk>sz[rt[i]])printf("2147483647\n");
            else printf("%d\n",kth(rt[i],lsrk+1)-vd);
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。