主席树POJ2104

求区间第k大数是多少

用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂

用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个树,由于加入一个数只需要log级别修改,所以建树效率很高。

主席树的精髓在于可持续化,就是说之前区间的信息不去修改它,递推加入新元素的时候,要新开log个空间来存储。因为主席树本身比较占用空间,只需改变这些空间的指向就可以重复利用不变的空间,达到节省空间的目的。

简而言之,主席树是一种重复利用数据不变的空间,建成空间上只有一颗完整的树,但逻辑上是多颗树同时共存的数据结构。

他具有线段树的查询效率。

更大的好处是,在处理某些问题上更符合人类的思维,树的同层之间有很好的性质。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
struct node
{
    int id,val;
}s[100005];
int b[100005],cnt,root[100005];
bool cmp(const node &a,const node &b)
{
    return a.val<b.val;
}
struct node1
{
    int l,r,val;
}tree[100005*20];
int build(int l,int r)
{
    cnt++;
    int now=cnt;
    tree[now].val=0;
    if(l==r)
    return now;
    int mid=(l+r)>>1;
    tree[now].l=build(l,mid);
    tree[now].r=build(mid+1,r);
    return now;
}
void up(int now)
{
    tree[now].val=(tree[tree[now].l].val+tree[tree[now].r].val);
}
int update(int ori,int l,int r,int x)
{
    cnt++;
    int now=cnt;
    tree[now]=tree[ori];
    if(l==r)
    {
        tree[now].val++;
        return now;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    tree[now].l=update(tree[ori].l,l,mid,x);
    else
    tree[now].r=update(tree[ori].r,mid+1,r,x);
    up(now);
    return now;
}
int query(int l,int r,int ox,int oy,int k)
{
    if(l==r)
    return l;
    int res = tree[tree[oy].l].val- tree[tree[ox].l].val;
    int m = (l+r)/2;
    if(k <= res)
    return query(l,m,tree[ox].l,tree[oy].l,k);
    else
    return query(m+1,r,tree[ox].r,tree[oy].r,k-res);
}
int main()
{
    int n,q;
    while(cin>>n>>q)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s[i].val);
            s[i].id=i;
        }
        sort(s+1,s+1+n,cmp);
        for(int i=1;i<=n;i++)
        b[s[i].id]=i;
        cnt=0;
        root[0]=build(1,n);
        for(int i=1;i<=n;i++)
        {
            root[i]=update(root[i-1],1,n,b[i]);
        }
        while(q--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            int id=query(1,n,root[a-1],root[b],c);
            printf("%d\n",s[id].val);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

Scala兴衰史:暂时的没落或许是一个新的开始

5年前,Scala 似乎曾要成为编程语言中下一个佼佼者,因为它能够优雅得使用面向对象编程范式进行函数编程。 现如今,随着像 LinkedIn 和 Yammer ...

3714
来自专栏take time, save time

Think in 递归

     网上写递归的文章可以用汗牛充栋来形容了,大多数都非常清晰而又细致的角度上讲解了递归的概念,原理等等。以前学生的时候,递归可以说一直是我的某种死穴,原理...

41312
来自专栏企鹅号快讯

C+虚函数实现多态性的思考

相信这篇文字已经被这个晦涩的标题直接给PASS了,但笔者想把这些晦涩的概念说的生动些,C++和Python在编程思想上有很多是一致的,比如面向对象的思想,面向对...

21310
来自专栏程序员互动联盟

【面试宝典】谈谈面向对象

面试官:知道面向对象吧。 小白:嗯,知道,面想对象就是封装继承多态呀。 面试官:回答了一部分,还能谈谈除了封装、继承、多态之外的吗,比如说怎么抽象,抽象的思想是...

4048
来自专栏企鹅号快讯

编程世界的沟沟坎坎

我相信每一个想学习编程或者经历过编程实践的人,在刚开始的时候都会遇到一些沟沟坎坎,尤其是对编程里面的一些概念,比如说Java语言是面向对象的、C语言是面向过程的...

2249
来自专栏Aloys的开发之路

关于强制式(命令式)语言和声明式语言的区别

在阅读Alfred V.Aho等的大作Compilers Principles,Techniques and Tools是看到如下一段话: Another  c...

2835
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1223
来自专栏aCloudDeveloper

算法导论第二章小试牛刀

Author: bakari   Date: 2015.9.11 《算法导论》真是一本让人又爱又恨的书,爱自然是因为它精简凝练的算法呈现,读来让人欲罢不能;至于...

28210
来自专栏Python小屋

Python实现大自然数分解为最多4个平方数之和(1)

问题描述:任意大自然数,总是能分解为最多4个平方数的和,所谓平方数是指它是一个自然数的平方。例如:72884 = 4^2 + 138^2 + 232^2,337...

2734
来自专栏ACM算法日常

I'm Telling the Truth(二分图)- HDU 3729

二分图:设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点...

904

扫码关注云+社区

领取腾讯云代金券