首页 > 其他 > 详细

BZOJ4923 [Lydsy1706月赛]K小值查询

时间:2019-01-12 13:42:05      阅读:138      评论:0      收藏:0      [点我收藏+]

题意

维护一个长度为n的正整数序列a_1,a_2,...,a_n,支持以下两种操作:
1 k,将序列a从小到大排序,输出a_k的值。
2 k,将所有严格大于k的数a_i减去k。

\(n \leq 10^5\)

分析

考虑用Treap来维护数的排名。感官上有些数修改之后的相对排名时不会变的。

考虑1到k的数不会被修改。k+1到2k的数修改之后会和前面的数排名交叉,2k+1到inf的数修改后相对排名不变。后面的数打个标记即可。中间的数至少会减少一半,暴力修改插入即可。权值只减不增,类似启发式合并的摊还分析一样,一个数最多会被这样减小\(O(\log n)\)次。

时间复杂度\(O(n \log^2 n)\)

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
template<class T>il T read(rg T&x)
{
    return x=read<T>();
}
typedef long long ll;

co int N=1e5+7;
int root;
int tot;
namespace T
{
    int ch[N][2],siz[N];
    int val[N],sub[N];
    int pri[N];
    
    int newnode(int v)
    {
        int x=++tot;
        ch[x][0]=ch[x][1]=0,siz[x]=1;
        val[x]=v,sub[x]=0;
        pri[x]=rand();
        return x;
    }
    
    void pushup(int x)
    {
        siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];
    }
    
    void pushdown(int x)
    {
        if(sub[x])
        {
            if(ch[x][0])
            {
                sub[ch[x][0]]+=sub[x];
                val[ch[x][0]]-=sub[x];
            }
            if(ch[x][1])
            {
                sub[ch[x][1]]+=sub[x];
                val[ch[x][1]]-=sub[x];
            }   
            sub[x]=0;
        }
    }
    
    void split(int x,int v,int&l,int&r)
    {
        if(!x)
        {
            l=r=0;
            return;
        }
        if(val[x]<=v)
        {
            l=x;
            pushdown(l);
            split(ch[l][1],v,ch[l][1],r);
            pushup(l);
        }
        else
        {
            r=x;
            pushdown(r);
            split(ch[r][0],v,l,ch[r][0]);
            pushup(r);
        }
    }
    
    int merge(int x,int y)
    {
        if(!x||!y)
            return x+y;
        if(pri[x]>pri[y])
        {
            pushdown(x);
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);
            return x;
        }
        else
        {
            pushdown(y);
            ch[y][0]=merge(x,ch[y][0]);
            pushup(y);
            return y;
        }
    }
    
    void insert(int&t,int v)
    {
        int x,y;
        split(t,v,x,y);
        t=merge(x,merge(newnode(v),y));
    }
    
    void inserts(int&t,int x)
    {
        if(!x)
            return;
        pushdown(x);
        inserts(t,ch[x][0]);
        inserts(t,ch[x][1]);
        ch[x][0]=ch[x][1]=0,siz[x]=1;
        int l,r;
        split(t,val[x],l,r);
        t=merge(l,merge(x,r));
    }
    
    void change(int&t,int v)
    {
        int x,y,z;
        split(t,v,x,y);
        if(y)
        {
            sub[y]+=v;
            val[y]-=v;
        }
        split(y,v,y,z);
        inserts(x,y);
        t=merge(x,z);
    }
    
    int kth(int&t,int k)
    {
        pushdown(t);
        if(k==siz[ch[t][0]]+1)
            return val[t];
        if(k<=siz[ch[t][0]])
            return kth(ch[t][0],k);
        else
            return kth(ch[t][1],k-siz[ch[t][0]]-1);
    }
}
using namespace T;
using namespace std;

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    srand(20030506);
    int n,m;
    read(n),read(m);
    while(n--)
        insert(root,read<int>());
    while(m--)
    {
        int opt,k;
        read(opt),read(k);
        if(opt==1)
            printf("%d\n",kth(root,k));
        else
            change(root,k);
    }
    return 0;
}

BZOJ4923 [Lydsy1706月赛]K小值查询

原文:https://www.cnblogs.com/autoint/p/10259329.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!