1. 题目

传送门= ̄ω ̄=

更新:突然发现LUOGU上有这题(LUOGU – 2617),可以木有权限号刷~传送门= ̄ω ̄=

题目大意:

给你一个序列,要求资磁两个操作:

  • 将某一个位置的数字改变
  • 询问一段区间内第k小的数字

操作数和序列长度均在10000的范围内,无多组数据。

2. 题解

首先如果不带修改的区间第k小(大)问题我已经写过两个题解了:

如果带修改怎么办呢?

  1. 听说可以树状数组套主席树$O(mlog_2^2n)$做,然而我不会QvQ
  2. 借鉴上面的二分答案套线段树的静态k小数做法,我们可以把线段树对应的那一段段数组区间换成一颗颗splay来资磁修改!

具体思路懒得讲了,上面那篇博客(二分套线段树)中讲过惹。。。

算法复杂度是$O(mlog_2^3n)$

直接放代码吧(我懒你咬我啊?),我会附上注释的=。=

PS:没想到这玩意也不难打,一开始以为至少两三百行,结果最后才140多行,而且还一遍AC惹!爽啊♂~

代码:

#include <bits/stdc++.h>
#define SZ (10005)//数据范围
#define LS(a) (a<<1)//线段树节点a的左儿子的编号
#define RS(a) (a<<1|1)//线段树节点a的右儿子的编号
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)//读入优化
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{int f,s[2],d,sz;}e[SZ*400];//splay节点结构体
int cnt,n,m,a[SZ],data[SZ],td[2][SZ],lv[SZ],A,B,C,lim1,lim2;
//cnt是splay(已申请的)节点个数,data是用来排序建splay的数组,td是归并排序的暂存数组
//lv[i]是对应区间[i,i]的线段树节点的编号(可以实现修改不递归),lim1是二分答案下界,lim2是上界
char opt[5];//存Q还是C(操作类型)
stack<int> st;//splay的垃圾回收栈
int MKN()//splay的申请新节点操作
{
    int tmp;
    if(st.empty())tmp=++cnt;
    else tmp=st.top(),st.pop();
    memset(&e[tmp],0,sizeof(N));
    return tmp;
}
int pos(int a){return e[e[a].f].s[1]==a;}//判断splay中某一节点是左儿子还是右儿子
void pup(int a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}//splay的push_up
void rot(int a)//splay的rotate
{
    int f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
int build(int l,int r,int fa)//新建一颗splay
{
    if(l>r)return 0;
    int a=MKN(),mid=(l+r)>>1;e[a].f=fa,e[a].d=data[mid];
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a),pup(a);
    return a;
}
struct splay_tree//splay结构体
{
    int root;//根节点
    void splay(int a,int t)//splay的splay操作=。=
    {
        for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
            if(pos(a)^pos(e[a].f))rot(a);
            else rot(e[a].f);
        if(!t)root=a;
    }
    int find_by_key(int key,int a)//按键值找节点
    {
        if(!a)return 0;
        if(key==e[a].d)return a;
        if(key<e[a].d)return find_by_key(key,e[a].s[0]);
        return find_by_key(key,e[a].s[1]);
    }
    void del(int d)//删除值为d的节点(有多个则只删除一个)
    {
        int p=find_by_key(d,root),l,r;
        splay(p,0),l=e[p].s[0],r=e[p].s[1];
        e[p].s[0]=e[p].s[1]=e[l].f=e[r].f=0;
        while(e[l].s[1])l=e[l].s[1];
        while(e[r].s[0])r=e[r].s[0];
        splay(l,0),splay(r,0);
        e[r].s[0]=l,e[l].f=r,pup(l),pup(r),root=r,st.push(p);
    }
    void insert(int d,int fa,int&a)//插入一个值为d的节点
    {
        if(!a){a=MKN(),e[a].d=d,e[a].f=fa,e[a].sz=1,splay(a,0);return;}
        if(d<e[a].d)return insert(d,a,e[a].s[0]);
        return insert(d,a,e[a].s[1]);
    }
    int order_of_key(int d)//询问该splay中比d要小的数字有多少个(不含d)
    {
        int a=root,tot=0;
        while(a)
            if(e[a].d<d)tot+=e[e[a].s[0]].sz+1,a=e[a].s[1];
            else a=e[a].s[0];
        return tot-1;//因为有哨兵节点所以要-1返回
    }
}tree[SZ<<2];
void sbuild(int l,int r,int a)//线段树建树
{
    if(l==r)
    {
        int t1=data[l-1],t2=data[r+1];
        data[l-1]=INT_MIN,data[r+1]=INT_MAX;
        lv[l]=a,tree[a].root=build(l-1,r+1,0);//这里l-1,r+1是splay的哨兵节点
        data[l-1]=t1,data[r+1]=t2;
        return;
    }
    int mid=(l+r)>>1;
    sbuild(l,mid,LS(a)),sbuild(mid+1,r,RS(a));
    for(int i=l;i<=mid;i++)td[0][i]=data[i];
    for(int i=mid+1;i<=r;i++)td[1][i]=data[i];
    td[0][mid+1]=td[1][r+1]=INT_MAX;
    for(int i=l,p=l,q=mid+1;i<=r;i++)
        if(td[0][p]<=td[1][q])data[i]=td[0][p++];
        else data[i]=td[1][q++];
    //上面是归并排序=。=
    int t1=data[l-1],t2=data[r+1];
    data[l-1]=INT_MIN,data[r+1]=INT_MAX;
    tree[a].root=build(l-1,r+1,0);//这里l-1,r+1是splay的哨兵节点
    data[l-1]=t1,data[r+1]=t2;
}
int query(int l,int r,int d,int L,int R,int a)//询问区间l,r中,小于d的数字有多少个
{
    if(l<=L&&R<=r)return tree[a].order_of_key(d);
    int mid=(L+R)>>1,tot=0;
    if(l<=mid)tot+=query(l,r,d,L,mid,LS(a));
    if(r>mid)tot+=query(l,r,d,mid+1,R,RS(a));
    return tot;
}
void update(int pos,int d)//修改序列的第pos项为d
{
    for(int p=lv[pos];p;p>>=1)
        tree[p].del(a[pos]),tree[p].insert(d,0,tree[p].root);
    a[pos]=d,lim1=min(lim1,d),lim2=max(lim2,d);
}
void work()//询问操作
{
    int l=lim1,r=lim2,mid;
    while(l!=r)
    {
        mid=(l+r+1)>>1;
        int tmp=query(A,B,mid,1,n,1);
        if(tmp<C)l=mid;else r=mid-1;
    }
    printf("%d\n",l);
}
int main()
{
    IN(n),IN(m),lim1=INT_MAX,lim2=INT_MIN,e[0].d=INT_MAX;
    for(int i=1;i<=n;i++)
        IN(a[i]),data[i]=a[i],lim1=min(lim1,a[i]),lim2=max(lim2,a[i]);
    sbuild(1,n,1);
    while(m--)
    {
        scanf("%s",opt),IN(A),IN(B);
        if(opt[0]=='C')update(A,B);
        else IN(C),work();
    }
    return 0;
}

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *