主席树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 条评论
登录 后参与评论

相关文章

  • codeforces 438D

    在某位不知名的大大推荐下做了这题,和我上一篇的线段树很像,于是怒拍,思想基本相同,记录区间最大值,当最大值小于取模时可以剪枝。 今后再遇到此类问题算是能解决了 ...

    triplebee
  • HDU4027

    本以为对线段树还是比较熟悉的,但是这题改变了我的想法。 顺着wk的题解做了这题。 拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那...

    triplebee
  • POJ1839

    //终于做出来第一题扫描线了,纠结了好久,纪念一下 //关键在于画图理解 #include<iostream> #include<algorithm> usi...

    triplebee
  • HDU4027

    本以为对线段树还是比较熟悉的,但是这题改变了我的想法。 顺着wk的题解做了这题。 拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那...

    triplebee
  • codeforces 438D

    在某位不知名的大大推荐下做了这题,和我上一篇的线段树很像,于是怒拍,思想基本相同,记录区间最大值,当最大值小于取模时可以剪枝。 今后再遇到此类问题算是能解决了 ...

    triplebee
  • 洛谷P3808 【模板】AC自动机(简单版)

    subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;

    attack
  • Leetcode 77 Combinations

    Given two integers n and k, return all possible combinations of k numbers out o...

    triplebee
  • C++二分图代码实现

    #include <iostream> #include <cstdio> #include <vector> using namespace std; #d...

    kalifa_lau
  • LeetCode Contest 181

    遍历除数的时候从1到sqrt(nums[i]) 10000*sqrt(100000) 是不会超时的

    ShenduCC
  • qt5中信号和槽的新语法

    蘑菇先生

扫码关注云+社区

领取腾讯云代金券