求助

P6136 【模板】普通平衡树(数据加强版)

optimize_2 @ 2020-02-27 12:19:15

本来想着白嫖,结果炸了

#include<bits/stdc++.h>
#define maxn (int)3e7
using namespace std;

inline char nextchar();
inline int read(char type);
inline void write(int x);

int c[(int)5e7+10];

int n,opt,a,last;

inline int lowbit(int x) {
    return x&(-x);
}

inline void add(int pos,int x) {
    while(pos<=maxn) c[pos]+=x,pos+=lowbit(pos);
}

void build() {
    for(int i=1;i<=n;i++) {
        int t;cin>>t;add(t,1);
    }
}

inline int myrank(int x) {
    int res=1;x--;
    while(x) res+=c[x],x-=lowbit(x);
    return res; 
}

inline int findKth(int k) {
    int ans=0,cnt=0;
    for(int i=30;i>=0;i--) {
        ans+=(1<<i);
        if(ans>maxn||cnt+c[ans]>=k) ans-=(1<<i);
        else cnt+=c[ans];
    }
    return ++ans;
}

inline int pre(int x) {return findKth(myrank(x)-1);}
inline int nxt(int x) {return findKth(myrank(x+1));}

int main() {
    n=read('c');
    for(register int i=1;i<=n;i++) {
        opt=read('c'),a=read('c');
        a^=last;
        a+=(int)1e7+10;
        switch(opt)
        {
        case 1:
            add(a,1);
            break;
        case 2:
            add(a,-1);
            break;
        case 3:
            write(myrank(a));
            putchar('\n');
            break;
        case 4:
            write(findKth(a-(int)1e7-10)-(int)1e7-10);
            putchar('\n');
            break;
        case 5:
            write((int)pre(a)-(int)1e7-10);
            putchar('\n');
            break;
        case 6:
            write(nxt(a)-(int)1e7-10);
            putchar('\n');
            break;
        }
    }
}

inline char nextchar() {
    static char buf[100000],*p1=buf, *p2=buf;
    return (p1 == p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline int read(char type) {
    if(type=='f') {
        int p=0;
        char ch=0;
        bool sign=false;
        while (!isdigit(ch)) {
            sign|=(ch=='-');
            ch=nextchar();
        }
        while(isdigit(ch)) {
            p=p*10+(ch^48);
            ch=nextchar();
        }
        p=sign?-p:p;
        return p;
    } else {
        int x=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {
            if(ch=='-') {
                f=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
}

inline void write(int x) {
    last=x;
    static int stk[100],top=0;
    if(x==0) {
        putchar('0'); return;
    }
    if(x<0) {
        x=-x;
        putchar('-');
    }
    while(x) {
        stk[++top]=x%10;
        x/=10;
    }
    while(top) putchar(stk[top--]+'0');
}

by Belarus @ 2020-02-27 12:22:39

输入格式变了吧


by registerGen @ 2020-02-27 12:22:48

你读题了吗 @optmize_2


by Belarus @ 2020-02-27 12:23:05

有初始的数


by VTloBong @ 2020-02-27 12:25:38

@optmize_2 强制在线了


|