链接：

https://vjudge.net/problem/POJ-2104#author=malic

题意：

给定一个数组 a[1...n]，数组元素各不相同，你的程序要对每次查询Q(i,j,k)作出回答，其中Q(i,j,k)的含义为在数组a[i...j]中第k大的数字.

例如，给出数组a=(1, 5, 2, 6, 3, 7, 4).查询语句为Q(2, 5, 3)，即从(5,2,6,3)中找出第3大的元素，将之排序得到(2, 3, 5, 6)，故第三大的数字是5，所以这次查询的结果应当为5.

思路：

主席树模板。

代码：

#include <iostream>

#include <cstdio>

#include <vector>

#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

using namespace std;

typedef long long LL;

const int MAXN = 1e5+10;

struct Node

{

    int v;

    int pos;

    bool operator < (const Node& that)const

    {

        return this->v < that.v;

    }

}node[MAXN];

int Sca[MAXN], Ori[MAXN];

struct Segment

{

    int l, r;

    int cnt;

}Seg[MAXN*30];

int Tree_root[MAXN*30];

int cnt = 0, tree_cnt = 0;

int n, m;

int Insert(int num, int last, int l, int r)

{

    ++tree_cnt;//树节点数加1

    Seg[tree_cnt].cnt = Seg[last].cnt+1;//数加1

    int nownode = tree_cnt;//记录当前节点数用于返回

    int mid = (l+r)/2;

    if (l == r)

    {

        return nownode;

    }

    else if (num <= mid)

    {

        Seg[nownode].l = Insert(num, Seg[last].l, l, mid);

        Seg[nownode].r = Seg[last].r;

    }

    else

    {

        Seg[nownode].l = Seg[last].l;

        Seg[nownode].r = Insert(num, Seg[last].r, mid+1, r);

    }

    return nownode;

}

int Query(int x, int y, int l, int r, int k)

{

//    cout << Seg[x].cnt << ' ' << Seg[y].cnt << ' ' << l << ' ' << r << endl;

    if (l == r)

        return l;

    int sum = (Seg[Seg[y].l].cnt - Seg[Seg[x].l].cnt);

    int mid = (l+r)/2;

    if (k <= sum)

        return Query(Seg[x].l, Seg[y].l, l, mid, k);

    else

        return Query(Seg[x].r, Seg[y].r, mid+1, r, k-sum);

}

void scatter()

{

    //离散化

    cnt = 0;

    int pos = 0;

    sort(node+1, node+1+n);

    Ori[++pos] = node[1].v;

    Sca[node[1].pos] = ++cnt;

    for (int i = 2;i <= n;i++)

    {

        if (node[i].v == node[i-1].v)

        {

            Sca[node[i].pos] = cnt;

        }

        else

        {

            Sca[node[i].pos] = ++cnt;

            Ori[++pos] = node[i].v;

        }

    }

}

int main()

{

    scanf("%d %d", &n, &m);

    for (int i = 1;i <= n;i++)

        scanf("%d", &node[i].v), node[i].pos = i;

    scatter();

    Tree_root[0] = 0;

    Seg[0].cnt = 0;

    for (int i = 1;i <= n;i++)

    {

        int pos = Insert(Sca[i], Tree_root[i-1], 1, n);

        Tree_root[i] = pos;

    }

    while (m--)

    {

        int x, y, k;

        scanf("%d %d %d", &x, &y, &k);

        int pos = Query(Tree_root[x-1], Tree_root[y], 1, n, k);

        printf("%d\n", Ori[pos]);

    }

    return 0;

}

/*

7 3

1 5 2 6 3 7 4

2 5 3

4 4 1

1 7 3

*/

巴特西

POJ-2104-Kth Number（主席树）

链接：

题意：

思路：

代码：

最新文章

热门文章