rt

同学写的 Splay 过了，我换成 fhq 就 WA 了

link1 link2

#include <unordered_map>
#include <iostream>
#include <cstdlib>
#include <cstdio>

#define LL long long
#define N 200001

using namespace std;
int q; LL k;
unordered_map<LL,bool> mp;

int rt,tcnt;
struct Tree { LL val,mn,mx; int key,ans,mnans,mxans,ls,rs,siz; }t[N];

void upd(int x) {
    t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
    t[x].mn=t[x].mx=t[x].val,t[x].ans=t[x].mxans=t[x].mnans=1;
    if (t[x].ls) t[x].mn=t[t[x].ls].mn,t[x].mnans=t[t[x].ls].mnans;
    if (t[x].rs) t[x].mx=t[t[x].rs].mx,t[x].mxans=t[t[x].rs].mxans;
    if (t[x].ls and t[x].val-t[t[x].ls].mx<=k) t[x].ans+=t[t[x].ls].mxans;
    if (t[x].rs and t[t[x].rs].mn-t[x].val<=k) t[x].ans+=t[t[x].rs].mnans;
    if (!t[x].ls or (t[t[x].ls].mnans==t[t[x].ls].siz and t[x].val-t[t[x].ls].mx<=k)) t[x].mnans=t[x].ans;
    if (!t[x].rs or (t[t[x].rs].mxans==t[t[x].rs].siz and t[t[x].rs].mn-t[x].val<=k)) t[x].mxans=t[x].ans;
}

void merge(int &rt,int x,int y) {
    if (!x or !y) return rt=x+y,void();
    if (t[x].key<=t[y].key) rt=x,merge(t[rt].rs,t[x].rs,y);
    else rt=y,merge(t[rt].ls,x,t[y].ls);
    upd(rt);
}

void split(int rt,int &x,int &y,int val) {
    if (!rt) return x=y=0,void();
    if (t[rt].val<=val) x=rt,split(t[rt].rs,t[x].rs,y,val),upd(x);
    else y=rt,split(t[rt].ls,x,t[y].ls,val),upd(y);
}

void ins(LL val) {
    int x=0,y=0,z=++tcnt; t[z]={val,val,val,rand(),1,1,1,0,0,1};
    split(rt,x,y,val); merge(x,x,z); merge(rt,x,y);
}

void del(LL val) {
    int x=0,y=0,z=0;
    split(rt,x,y,val); split(x,x,z,val-1); merge(rt,x,y);
}

int ask(LL val) {
    int x=0,y=0,res=0;
    split(rt,x,y,val);
    res=t[x].mxans+(t[y].mn-t[x].mx<=k?t[y].mnans:0);
    merge(rt,x,y);
    return res;
}

int main() {
    srand(388651);
    scanf("%d%lld",&q,&k);
    for (int i=1;i<=q;i++) {
        int op; LL x;
        scanf("%d%lld",&op,&x);
        if (op==1) {
            if (mp[x]) del(x),mp[x]=0;
            else ins(x),mp[x]=1;
        } else printf("%d\n",ask(x));
    }
    return 0;
}