1. 题目

传送门= ̄ω ̄=

题目大意:

  • 给一个静态序列,再给出n个操作,每个操作为求一个区间内第k小的数字是多少

2. 题解

以前写过一个二分套线段树的题解:传送门= ̄ω ̄=(题目一样,就是那个有多组数据这个没有)

那个复杂度是$O(mlog_2^3n)$,比较慢

现在要讲的是主席树の做法,复杂度$O(mlog_2n)$

先讲思路:

首先,如果我们要查询某段区间内的第k小数,我们可以采用二分答案!每次二分一个答案,判断这个数字在区间内排第几。比如我们有一个序列:$43241$,我们查询区间$[2,5]$(即$3241$ )内排名第$2$的是谁。我们先二分一个答案,比如是$4$,发现$4$排名为$4$,所以答案比$4$小。再二分,比如是$1$ (鬼知道它怎么二分成这样的),发现$1$排名为$1$,所以答案比$1$大。这样下去就能找到最后答案为$2$!

介于这个思想,我们用主席树来实现!

先对原序列$a$(大小为$n$)进行排序、去重得到序列$h$,设序列$h$内元素个数为$tot$。我们对序列$a$的前缀$1,2,3,…,i(1\leq i\leq n)$分别建立一颗线段树(注意这里是线段树),一共有$n$颗线段树。第$i$颗线段树保存的是序列$h$中的每个元素各在$a$的前缀$1,2,3,…,i$中出现了多少次!

比如序列$a=45634$,那么$h=3456$,则线段树对应表如下:

第几颗 对应序列
1 0100(增加了数字4)
2 0110(增加了数字5)
3 0111(增加了数字6)
4 1111(增加了数字3)
5 1211(增加了数字4)

大概看懂了吧,我尽力惹QvQ

然后,比如我们要查询上面那个序列$a=45634$的区间$[2,5]$中的第$2$小的数字是谁,于是我们拿出第$2-1=1$颗线段树和第$5$颗线段树,如图:

t1

看懂了咩?其实就是俩维护区间和的线段树啊!(对应序列关系见上面的表格)

我们现在查第$2$小数嘛,于是我们先到俩线段树的根节点看。根节点的左右儿子分别对应着$h$序列的区间$[1,2]$和$[3,4]$,也就是$34$和$56$。可以看出来——在原序列$a=45634$的区间$[2,5]$(即$5634$)中,34一共出现了2次(3有1次,4有1次),正好是俩根节点的左儿子的权值之差($3-1=2$)。而56在区间$[2,5]$中一共出现了2次(5有1次,6有1次),正好是俩根节点的右儿子的权值之差($2-0=2$)。所以我们可以轻松得到:在区间$[l,r]$中,小于等于4的数字有2个,大于4的数字有2个。所以——我们就能知道——排名为$2$的数字一定是在根节点的左儿子对应的区间内的!(3和4)

然后我们进入根节点的左儿子,发现——它的左儿子是对应序列$h$中的3,它的右儿子对应的是序列$h$中的4,其中小于等于$3$的有$1-0=1$个,而大于$3$的有$2-1=1$个(注意观察上图中的线段树),因此排名为2的数字在它的右儿子节点对于的$h$序列区间中。

于是我们得到了最终答案——$h[2]=4$

这就是整个算法的全部原理。

由于我们需要$n$颗线段树,但是显然没有这么多空间、时间,所以我们用可持久化线段树——主席树

主席树原理我就不讲了,以后有空再总结一下了。

先安利一波教程(我在B站学算法QvQ):传送门= ̄ω ̄=

好吧,讲了这么多,放个代码:

#include <cstdio>
#include <climits>
#include <cctype>
#include <algorithm>
#define NS (100005)
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 l,r,d;}t[NS*40];
int n,m,a[NS],h[NS],top,root[NS],cnt;
int H(int a){return lower_bound(h+1,h+1+top,a)-h;}
void update(int l,int r,int&x,int y,int pos)
{
    x=++cnt,t[x]=t[y],t[x].d++;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
    else update(mid+1,r,t[x].r,t[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)return l;
    int mid=(l+r)>>1,tmp=t[t[y].l].d-t[t[x].l].d;
    if(tmp>=k)return query(l,mid,t[x].l,t[y].l,k);
    return query(mid+1,r,t[x].r,t[y].r,k-tmp);
}
int main()
{
    IN(n),IN(m),h[0]=INT_MAX;
    for(int i=1;i<=n;i++)IN(a[i]),h[i]=a[i];
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++)if(h[i]!=h[i-1])h[++top]=h[i];
    for(int i=1;i<=n;i++)update(1,n,root[i],root[i-1],H(a[i]));
    for(int i=1,a,b,k;i<=m;i++)
        IN(a),IN(b),IN(k),printf("%d\n",h[query(1,n,root[a-1],root[b],k)]);
    return 0;
} 
分类: 所有

XZYQvQ

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

3 条评论

konnyakuxzy · 2018年1月7日 2:23 下午

QvQ可是,,,您那篇文章会不会,,
不具有学术性&普遍性啊,这。。。
尴尬

Sys_Con · 2018年1月7日 11:10 上午

%%%Orz
—来自刚学Splay的真蒟蒻

    konnyakuxzy · 2018年1月7日 12:01 下午

    QvQ Orz
    我才是超级辣鸡啊=。=
    连冬令营都没进QvQ
    我太菜惹QvQ。。。

      Kinandra · 2018年1月7日 2:05 下午

      蒟蒻+1

      Sys_Con · 2018年1月7日 2:06 下午

      捕获一只谦虚daolao

        konnyakuxzy · 2018年1月7日 2:10 下午

        Orz泥萌太强惹,吓得我瑟瑟发抖不敢吱声QvQ

    Kinandra · 2018年1月7日 2:06 下午

    SYSCON大师其实强的一毛

      Kinandra · 2018年1月7日 2:07 下午

      不过我才是吧爸爸

        Kinandra · 2018年1月7日 2:08 下午

        请忽略‘吧字‘

          konnyakuxzy · 2018年1月7日 2:11 下午

          Orz您太聚惹QvQ
          话说泥萌是肿么找到我のblog的啊?
          很好奇=。=

          Kinandra · 2018年1月7日 2:13 下午

          聚是J的意思吗?

          Kinandra · 2018年1月7日 2:14 下午

          追问追问

          konnyakuxzy · 2018年1月7日 2:15 下午

          啊,其实是巨佬的意思。
          所以。。。
          泥萌是肿么找到我のblog的啊?QAQ

          Kinandra · 2018年1月7日 2:17 下午

          是SYS_CON大神告诉我的

          konnyakuxzy · 2018年1月7日 2:19 下午

          不过不过,,,
          泥萌不会认识我吧?QvQ
          泥萌属于哪个学校啊QvQ?
          害怕.jpg

          Kinandra · 2018年1月7日 2:23 下午

          哈哈
          不如你猜一猜

litble · 2018年1月4日 3:40 下午

赶紧在新年第一篇博客上留名,orz大佬的主席树太强啦

    konnyakuxzy · 2018年1月4日 4:09 下午

    %%%KBdalao访问我的辣鸡博客,真是令我不胜感激Orz!
    我的主席树还太垃圾了啊,您还能树状数组套主席树花式解决动态kth问题Orz太强啦
    在新的一年里还是要多%%%kb来rp++!

      Kinandra · 2018年1月7日 2:12 下午

      xiang大神怎么发文章啊???

      Kinandra · 2018年1月7日 2:12 下午

      (蒟蒻发出了疑问)

        konnyakuxzy · 2018年1月7日 2:16 下午

        蛤?
        您认识我咩?
        QvQ害怕
        写文章的话登录以后顶部有一个“+新建”按钮
        点一下就行惹。
        markdown的

          Kinandra · 2018年1月7日 2:18 下午

          哦哦
          我当然知道你呀
          因为我是中情局的(划掉)

          Kinandra · 2018年1月7日 2:19 下午

          那它为什么总是”待发布“咩

          konnyakuxzy · 2018年1月7日 2:20 下午

          QvQ
          这这这么强QvQ
          不会是我太弱了影响了市容吧QvQ
          其实是真的可以划掉的

          konnyakuxzy · 2018年1月7日 2:21 下午

          QvQ我我我我这就去审核QvQ
          毕竟,,,审核还是有必要的QvQ。。。

          konnyakuxzy · 2018年1月7日 2:23 下午

          QvQ可是,,,您那篇文章会不会,,
          不具有学术性&普遍性啊,这。。。
          尴尬

          Kinandra · 2018年1月7日 2:24 下午

          那就不要了吧

          Kinandra · 2018年1月7日 2:24 下午

          谢谢

          Kinandra · 2018年1月7日 2:25 下午

          你应该认识kix6吧

          konnyakuxzy · 2018年1月7日 2:27 下午

          QvQ正在查找中Orz
          脑子不好使ing

          Kinandra · 2018年1月7日 2:28 下午

          ╮(╯▽╰)╭

          Kinandra · 2018年1月7日 2:32 下午

          好吧他其实是高三的大神

          konnyakuxzy · 2018年1月7日 2:36 下午

          Orz查不到QvQ
          痛苦不堪
          算惹算惹
          但是,,泥萌为啥认识我啊?
          我不是非常弱咩QvQ
          泥萌是一中的咩?

          Kinandra · 2018年1月7日 2:40 下午

          哈哈被你猜出来了
          你很强的呦

          konnyakuxzy · 2018年1月7日 2:44 下午

          Orz泥萌是,,,是,,,是高三dalao?
          Orz
          跪舔泥萌OrzOrzOrzOrz
          大神啊QvQ

          konnyakuxzy · 2018年1月7日 2:46 下午

          就说泥萌怎么会知道“J”
          QvQ
          太强了
          泥萌太jay了啊!
          专门跑到蒟蒻的blog来嘲讽蒟蒻Orz太jay了
          不过泥萌访问蒟蒻のblog我还是非常感激的啦!
          (*^__^*)

          Kinandra · 2018年1月7日 2:46 下午

          不是……

          Kinandra · 2018年1月7日 2:47 下午

          本蒟蒻还在splay的泥潭中挣扎

          konnyakuxzy · 2018年1月7日 2:50 下午

          ,,,
          想起来了
          NYHdalao&LXYdalao?
          Orz跳绳の神犇啊!
          QvQ太强惹
          爆踩我这种辣鸡蒟蒻QvQ

          Kinandra · 2018年1月7日 2:54 下午

          哎呀不是呀
          N大佬都去准备冬令营了

          Kinandra · 2018年1月7日 2:56 下午

          看着高一大佬总以为我是初三大佬
          不禁心生喜感

          Kinandra · 2018年1月7日 2:56 下午

          我不过是一个无名小卒

          Kinandra · 2018年1月7日 2:57 下午

          联赛差点一等都没了QAQ

          Kinandra · 2018年1月7日 2:59 下午

          不过LXYdalao在我旁边哦

          Kinandra · 2018年1月7日 3:00 下午

          你肯定不认识我的咩

          konnyakuxzy · 2018年1月7日 3:01 下午

          QvQ我不说话惹
          再膜下去我要把地球人全%一遍惹
          QvQ
          不过您QQ显示是,,,14岁???
          太强了%%%%Orz

          Kinandra · 2018年1月7日 3:09 下午

          啊啊暴露年龄了QAQ

          Kinandra · 2018年1月7日 3:40 下午

          X大佬在6机房咩??

          Kinandra · 2018年1月7日 3:42 下午

          大佬??
          在?
          回一句吧
          不耍大佬了

        konnyakuxzy · 2018年1月7日 6:14 下午

        Orz刚刚更新博客去啦~
        才看到Orz
        您耍我完全没问题的啦~QvQ
        但是您别说我是dalao啊,这样是在侮辱dalao这个词啊QAQ

发表评论

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

你是机器人吗? =。= *