[bzoj4923][splay]K small value query

4923: [Lydsy1706 race] K small value query

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 415 Solved: 121
[Submit][Status][Discuss]
Description

Maintain a sequence of positive integers of length n, a 1, a 2 , a, supports the following two operations:
1 k, sort the sequence a from small to large, and output the value of a_k.
2 k, K is subtracted from all numbers a ﹤ I that are strictly greater than k.
Input

The first row contains two positive integers, N, m (1 < = n, m < = 100000), representing the length of the sequence and the number of operations, respectively.
The second line contains n positive integers a, a, 2 , a n (1 < = a I < = 10 ^ 9), respectively representing each element in the sequence.
Next m lines, each line has two positive integers op (1 < = OP < = 2), K, if op=1, then 1 < = k < = n; if op=2, then 1 < = k < = 10 ^ 9; describe each operation in turn.
Output

Output several lines, for each query output a line an integer, that is, the k-th small value.
Sample Input

4 5

1 5 6 12

2 5

1 1

1 2

1 3

1 4
Sample Output

1

1

5

7

HINT

Source

Pay for this OJ

sol:

Consider using splay to maintain the ranking of numbers. Some of the sensory changes in the relative ranking will not change.
Consider that the number of 1 to k is not modified. After the number of k+1 to 2k is modified, it will cross with the previous number ranking. After the number of 2k+1 to inf is modified, the relative ranking will not change. Just mark the following numbers. The number in the middle will be reduced by at least half, and violent modification and insertion will be enough.

If you don't recycle memory like me, please open it up a bit. I adjusted it for 2 hours..

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
typedef double db;
int n,m;
inline int read()
{
    char c;
    int res,flag=0;
    while((c=getchar())>'9'||c<'0') if(c=='-')flag=1;
    res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0';
    return flag?-res:res;
}
const int N=5e6+7;
int val[N],lc[N],rc[N],fa[N],siz[N],cnt[N];
int tag[N];
inline void add(int x,int y)
{
    if(x)
    {
        val[x]+=y;
        tag[x]+=y;
    }
}
inline void tag_down(int x)
{
    if(tag[x])
    {
        add(lc[x],tag[x]);
        add(rc[x],tag[x]);
        tag[x]=0;
    }
}
inline void updata(int x)
{
    siz[x]=siz[lc[x]]+siz[rc[x]]+cnt[x];
}
inline void rotate(int x)
{
    int y=fa[x],z=fa[y];
    int b=lc[y]==x?rc[x]:lc[x];
    if(b) fa[b]=y;
    fa[x]=z;fa[y]=x;
    if(z)
    {
        if(lc[z]==y) lc[z]=x;
        else rc[z]=x;
    }
    if(rc[y]==x) rc[y]=b,lc[x]=y;
    else lc[y]=b,rc[x]=y;
    updata(y); 
}
int sta[N],rt;
inline void splay(int x,int f)
{
    sta[sta[0]=1]=x;
    for(int y=x;fa[y];y=fa[y]) sta[++sta[0]]=fa[y];
    while(sta[0]) tag_down(sta[sta[0]--]);
    while(fa[x]!=f)
    {
        if(fa[fa[x]]!=f)
        {
            if((lc[fa[fa[x]]]==fa[x])==(lc[fa[x]]==x)) rotate(fa[x]);
            else rotate(x);
        }
        rotate(x);
    } 
    updata(x);
    if(!f) rt=x;
}
inline int kth(int x,int y)
{
    while(true)
    {
        tag_down(x); 
        if(siz[lc[x]]>=y) x=lc[x];
        else if(siz[lc[x]]+cnt[x]>=y) return val[x];
        else y-=siz[lc[x]]+cnt[x],x=rc[x];
    }
}
int tot;
inline int insert(int x,int y)
{
    int now=rt,now2;
    while(now)
    {
        now2=now;
        tag_down(now);
        if(val[now]<x) now=rc[now];
        else if(val[now]>x) now=lc[now];
        else
        {
            cnt[now]+=y;
            splay(now,0);
            return now;
        }
    }
    ++tot;
    if(val[now2]<x) rc[now2]=tot;
    else lc[now2]=tot;
    val[tot]=x;
    fa[tot]=now2;
    cnt[tot]=y;
    splay(tot,0);
    return tot;
}
int a[N];
inline void build(int &k,int l,int r)
{
    int mid=l+r>>1;
    k=mid;
    val[k]=a[k];
    if(l<=mid-1) build(lc[mid],l,mid-1);
    if(mid+1<=r) build(rc[mid],mid+1,r);
    if(lc[k]) fa[lc[k]]=k;
    if(rc[k]) fa[rc[k]]=k; 
    updata(k);
}
int b;
int q[N],qr;
inline void sc(int x)
{
    if(!x) return;
    tag_down(x);
    if(lc[x]) sc(lc[x]);
    if(rc[x]) sc(rc[x]);
    q[++qr]=x;
    val[x]-=b;
    lc[x]=rc[x]=fa[x]=0;
}
inline void del(int x)
{
    if(cnt[x]>1)
    {
        cnt[x]--;
        return;
    }
    splay(x,0);
    if(!lc[x])
    {
        rt=rc[x];
        fa[rc[x]]=0;
        return;
    }
    if(!rc[x])
    {
        rt=lc[x];
        fa[lc[x]]=0;
        return;
    }
    rt=rc[x];
    fa[rc[x]]=0;
    int y=rc[x];
    tag_down(y);
    while(lc[y])
    {
        y=lc[y];
        tag_down(y);
    }
    lc[y]=lc[x];
    fa[lc[x]]=y;
    splay(lc[x],0);
}
inline void debug(int x)
{
    if(!x) return;
    tag_down(x);
    if(lc[x]) debug(lc[x]);
    printf("%d %d\n",val[x],cnt[x]);
    if(rc[x]) debug(rc[x]);
}
int main()
{
//  freopen("kth.in","r",stdin);
//  freopen("kth.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    a[0]=-1;
    a[++n]=0;
    sort(a+1,a+1+n);
    int nn=n;
    n=0;
    for(int i=1;i<=nn;++i)
    {
        if(a[i]!=a[i-1]) a[++n]=a[i];
        cnt[n]++;
    }
    build(rt,1,n);
    tot=n;
    int a;
    for(int j=1;j<=m;++j)
    {
        a=read();
        b=read();
//      debug(rt);
//      printf("\n");
        if(a==1)
        printf("%d\n",kth(rt,b+1));
        else
        {
            int x=insert(b,1);
            int y=insert(b*2+1,1);
            splay(x,0);
            splay(y,x);
            qr=0;
            sc(lc[y]);
            lc[y]=0;
            for(int i=1;i<=qr;++i) insert(val[q[i]],cnt[q[i]]);
            del(x);
            del(y);
            x=insert(b*2,1);
            add(rc[x],-b);
            del(x);
        }
    }
}

Posted on Sat, 04 Apr 2020 21:23:43 -0700 by ziong