BZOJ4923 K小值查询（splay）

时间：2023-03-09 19:34:07
BZOJ4923 K小值查询（splay）

　　容易想到建一棵平衡树，修改时打上标记即可。但是修改会导致平衡树结构被破坏。注意到实际上只有[k+1,2k)这一部分数在平衡树中的位置会被改变，所以对这一部分暴力修改，因为每次都会使其至少减小一半，复杂度非常正确。

　　开始写的玩意一个点要跑10s吓到我了，卡了半天常（最后也只是在darkbzoj上过了）造了半天bug，调的欲仙欲死，退役了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cassert>

using namespace std;

#define ll long long

#define N 100010

#define inf 2000000001

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],root,cnt;

struct data{int x,ch[],fa,s,lazy;

}tree[N<<];

inline void up(int k){tree[k].s=tree[lson].s+tree[rson].s+;}

inline void update(int k,int x){if (k) {if (tree[k].x<inf) tree[k].x-=x;tree[k].lazy+=x;}}

inline void down(int k){if (tree[k].lazy) update(lson,tree[k].lazy),update(rson,tree[k].lazy),tree[k].lazy=;}

inline void push(int k){if (tree[k].fa) push(tree[k].fa);down(k);}

inline int whichson(int k){return tree[tree[k].fa].ch[]==k;}

inline void move(int k)

{

    int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);

    tree[gf].ch[whichson(fa)]=k,tree[k].fa=gf;

    tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa;

    tree[k].ch[!p]=fa,tree[fa].fa=k;

    up(fa),up(k);

}

void splay(int k,int rt)

{

    push(k);

    while (tree[k].fa!=rt)

    {

        int fa=tree[k].fa;

        if (tree[fa].fa!=rt)

            if (whichson(k)^whichson(fa)) move(k);

            else move(fa);

        move(k);

    }

    if (!rt) root=k;

}

void build(int &k,int l,int r)

{

    if (l>r) return;

    int mid=l+r>>;

    k=++cnt;tree[k].x=a[mid],tree[k].s=r-l+;

    build(lson,l,mid-);build(rson,mid+,r);

    tree[lson].fa=tree[rson].fa=k;

}

int find(int k,int x)

{

    if (tree[lson].s+==x) return k;

    down(k);

    if (tree[lson].s+>x) return find(lson,x);

    else return find(rson,x-tree[lson].s-);

}

int qsuf(int k,int x)

{

    if (!k) return ;

    down(k);

    if (tree[k].x<x) return qsuf(rson,x);

    else

    {

        int t=qsuf(lson,x);

        return t&&tree[t].x<=tree[k].x?t:k;

    }

}

int qpre(int k,int x)

{

    if (!k) return ;

    down(k);

    if (tree[k].x>x) return qpre(lson,x);

    else

    {

        int t=qpre(rson,x);

        return t&&tree[t].x>=tree[k].x?t:k;

    }

}

void ins(int x)

{

    int k=root,fa=;

    while (k) down(k),tree[k].s++,fa=k,k=tree[k].x<=x?rson:lson;

    k=++cnt;tree[k].x=x,tree[k].s=,tree[k].fa=fa,tree[fa].ch[tree[fa].x<=x]=k;

    splay(k,);

}

void dfs(int k,int x)

{

    if (!k) return;

    down(k);

    ins(tree[k].x-x);

    dfs(lson,x),dfs(rson,x);

}

void modify(int x)

{

    int p=qpre(root,x),q=qsuf(root,*x);

    splay(p,);splay(q,p);

    int k=tree[q].ch[];tree[q].ch[]=;up(q);up(p);update(q,x);

    dfs(k,x);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4923.in","r",stdin);

    freopen("bzoj4923.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i]=read();

    a[]=,a[n+]=inf;sort(a,a+n+);

    build(root,,n+);

    for (int i=;i<=m;i++)

    {

        int op=read(),x=read();

        if (op==) printf("%d\n",tree[find(root,x+)].x);

        else modify(x);

    }

    return ;

}

相关文章