首页 > ACM题库 > HDU-杭电 > hdu 2665 Kth number-线段树-[解题报告]C++
2014
02-12

hdu 2665 Kth number-线段树-[解题报告]C++

Kth number

问题描述 :

Give you a sequence and ask you the kth big number of a inteval.

输入:

The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]

输出:

The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]

样例输入:

1 
10 1 
1 4 2 3 5 6 7 8 9 0 
1 3 2 

样例输出:

2

A的第一道可持续化线段树。
我是看这个看懂的http://hi.baidu.com/wyl8899/item/e00796a9cb2df73d020a4d68


可持续化线段树,主要思想就是利用历史信息,减少时间和内存花销。
比方有两棵线段树,但是他们只有一个节点信息不同。仔细一想,在这两颗线段树上,对应的 [l,r]节点  只有log(n)个节点不同。那么,除了不同的节点,其他节点信息,他们完全可以共用。


关于这题解法,我就复制别人的话了(  好懒啊 o(╯□╰)o )

考虑把权值离散化,然后用线段树解决问题。
对于一个询问(x,y,k),如果已经把a[x]..a[y]建成了一颗线段树,并维护区间和,显然二分就可以了。
(怎么二分? …看左儿子有没有k个然后递归 自己YY一下就出来了)
但是很遗憾我们没办法这么搞…这还不如裸奔…
接下来思考一个问题。
记T[x,y]为a[x]..a[y]建成的线段树,那么T[x,y]和T[1,x-1],T[1,y]有什么关系?
对于T[x,y]中的一个节点[L,R],我们一定可以在T[1,x-1]和T[1,y]中找到也代表[L,R]的对应节点。
考察这三个节点存储的区间和的关系,马上可以发现:
T[x,y]中任意节点[L,R]的区间和等于T[1,y]中对应节点的区间和减去T[1,x-1]中对应节点的区间和。
这就好办多了,我们只需要把所有的T[1,x](1<=x<=N)建出来了就可以了。
……
发现什么问题没有? 空间和时间都不允许你建N棵线段树的。
函数式数据结构的思想这时候派上用场了。
考察T[1,x]和T[1,x-1]——在T[1,x-1]加入a[x]就得到T[1,x]了。
单点修改的时候要改变信息的节点的数量是O(logn)。
于是我们"大胆地重用以前的信息",只新建这些节点,然后这些节点的左右儿子可以指向前一棵树的节点。
最终的总节点个数是O(nlogn),预处理复杂度O(nlogn),回答每个询问O(logn),常数还是有一点的。


//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
#include<iostream>
#include<ctime>
#include<map>
#include<set>
using namespace std;
#define MP(x,y) make_pair((x),(y))
#define PB(x) push_back(x)
typedef long long LL;
//typedef unsigned __int64 ULL;
/* ****************** */
const int INF=1000111222;
const double INFF=1e200;
const double eps=1e-8;
const LL mod=1000000007;
const int NN=100010;
const int MM=100010;
/* ****************** */

int a[NN],tf[NN],root[NN];
struct TR
{
    int ls,rs,sum;
}tr[NN*20];
int cnt;

int build(int l,int r)
{
    int id=++cnt;
    tr[id].sum=0;
    if(l!=r)
    {
        int mid=(l+r)>>1;
        tr[id].ls=build(l,mid);
        tr[id].rs=build(mid+1,r);
    }
    return id;
}

void push_up(int R)
{
    tr[R].sum=tr[ tr[R].ls ].sum + tr[ tr[R].rs ].sum;
}

int update(int x,int pre,int l,int r)
{
    int id=++cnt;
    tr[id].ls=tr[pre].ls;
    tr[id].rs=tr[pre].rs;
    tr[id].sum=tr[pre].sum;
    if(l==r)
    {
        tr[id].sum++;
        return id;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        tr[id].ls=update(x,tr[pre].ls,l,mid);
    else
        tr[id].rs=update(x,tr[pre].rs,mid+1,r);
    push_up(id);
    return id;
}

int query(int id1,int id2,int k,int l,int r)
{
    if(l==r)
        return l;
    int x=tr[ tr[id2].ls ].sum;
    x-=tr[ tr[id1].ls ].sum;
    int mid=(l+r)>>1;

  //  printf("now==[%d,%d]\n",l,r);
   // printf("[%d,%d] have %d\n",l,mid,x);

    if(x>=k)
        return query(tr[id1].ls,tr[id2].ls,k,l,mid);
    else
        return query(tr[id1].rs,tr[id2].rs,k-x,mid+1,r);
}

int main()
{
    int cas,n,m;
    int i,tol,x,st,en,k;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            tf[i]=a[i];
        }
        sort(tf+1,tf+1+n);
        tol=unique(tf+1,tf+1+n)-tf-1;
        cnt=0;
        root[0]=build(1,tol);

        for(i=1;i<=n;i++)
        {
            x=lower_bound(tf+1,tf+1+tol,a[i])-tf;
            root[i]=update(x,root[i-1],1,tol);
         //   printf("(%d,%d)%c",a[i],x,i==n?'\n':' ');
        }
        while(m--)
        {
            scanf("%d%d%d",&st,&en,&k);
            x=query(root[st-1],root[en],k,1,tol);
            printf("%d\n",tf[x]);
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/acmmaxx/article/details/18220987


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!