In The End

个人博客

0%

POJ2104题：分块与主席树

发表于 更新于 分类于 ，

题目

题目传送门：http://poj.org/problem?id=2104

K-th Number

Time Limit: 20000MS Memory Limit: 65536K
Total Submissions: 71694 Accepted: 25530
Case Time Limit: 2000MS

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n —- the size of the array, and m —- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values —- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it —- the k-th number in sorted a[i…j] segment.

Sample Input

1
2
3
4
5
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

1
2
3
5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

题解

多次查询[L,R]区间内第k大的数字的问题，这有两种做法，我最开始是拿分块做的，超时了，最近学主席树所以又做了一遍

首先是分块的代码，这道题用分块的话绝对是暴力美学，首先是对值进行枚举的暴力，然后就是常规的分块的暴力，总之莽就完了，不过代码打起来就相当舒适(相对于权值线段树来说)，然后就美美地超时了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=100010;

int block,num,l[maxn],r[maxn],belong[maxn],a[maxn],b[maxn],origin[maxn];

void build(int n){
    block=sqrt(n);
    num=n/block;
    if(n%block)
        num++;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        sort(b+l[i],b+r[i]+1);
}

int ask(int left,int right,int k,int n){
    int x,count,ans;
    for(int d=1;d<=n;d++) {
        x=a[d];
        count = 0;
        if (belong[left] == belong[right]) {
            for(int i=left;i<=right;i++)
                if(origin[i]<=x)
                    count++;
        } else {
            for(int i=left;i<=r[belong[left]];i++)
                if(origin[i]<=x)
                    count++;
            for (int i = belong[left] + 1; i <= belong[right] - 1; i++) {
                count += (int) (upper_bound(b + l[i], b + r[i] + 1, x) -
                                (b + l[i]));
                //cout << *upper_bound(b + l[i], b + r[i] + 1, x) << endl;
            }
            for(int i=l[belong[right]];i<=right;i++)
                if(origin[i]<=x)
                    count++;
        }
        if(count==k){
            ans=x;
            break;
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    int n,m,left,right,k;
    while(cin>>n>>m){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(origin,0,sizeof(origin));
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            origin[i]=b[i]=a[i];
        }
        sort(a+1,a+1+n);
        build(n);
        /*
        for(int i=1;i<=n;i++)
            cout << l[belong[i]] << ' ';
        cout << endl;
        */
        while(m--){
            cin>>left>>right>>k;
            if(left>right){int t=left;left=right;right=t;}
            cout << ask(left,right,k,n) << endl;
        }
    }
    return 0;
}

接下来上线段树的AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<vector>
#include<algorithm>
#define maxn 100000
using namespace std;

vector<int> dat[4*maxn + 50];    //线段树的数据
int a[maxn + 50];
int n, m;

//构建线段树
//k是节点的编号，和区间[l, r)对应
void build(int k, int l, int r)
{
    if (r - l == 1) {
        dat[k].push_back(a[l]); return;
    }
    int lc = k << 1, rc = k << 1 | 1;
    build(lc, l, (l + r) / 2);
    build(rc, (l + r) / 2, r);
    dat[k].resize(r - l);
    //利用STL的merge函数把两个儿子的数列合并
    merge(dat[lc].begin(), dat[lc].end(), dat[rc].begin(), dat[rc].end(),dat[k].begin());
}


int query(int i, int j, int x, int k, int l, int r)
{
    if (j <= l || r <= i)

        return 0;
    else if (i <= l&&r <= j){
        return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
    }
    else {
        //对儿子递归地计算
        int lc = query(i, j, x, k << 1, l, (l + r) / 2);
        int rc = query(i, j, x, k << 1 | 1, (l + r) / 2, r);
        return lc + rc;
    }
}

int search(int x, int y, int k)
{
    int l = -1000000000 - 1;
    int r = -l + 2;
    while (l < r){
        int mid = (l + r) >> 1;
        int num = query(x, y+1, mid, 1, 1, n+1);
        if (k <= num) r = mid;
        else{
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        build(1, 1, n + 1);
        int b, c, k;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &b, &c, &k);
            printf("%d\n", search(b, c, k));
        }
    }
    return 0;
}

主席树的话呢就是建立多个线段树的优化啦，我们把每个输入都当成更新，然后对每个更新都建立一个权值线段树，当我们查询[L,R]的区间第K大的数字时，我们只需要找到T[L-1]的权值线段树和T[R]的权值线段树，然后拿T[T[R].l]-T[T[L-1].l].sum(就是两者左子树数字的个数，假设答案为6，但是你要查的是第8大的数字，那么就是往两者的右子树上跑，否则就继续往两者的左子树上跑，有点烧脑哈，需要意会)

这个博客里细讲太麻烦了，我就直接上代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=(int)1e5+10;

struct node{
    int l,r,sum;
}T[maxn<<5];

int root[maxn],a[maxn],n,m,cnt;

vector<int> v;
int getid(int x){
    return (int)(lower_bound(v.begin(),v.end(),x)-v.begin()+1);
}

void update(int l,int r,int &x,int y,int k){
    T[++cnt]=T[y];T[cnt].sum++,x=cnt;
    if(l==r)
        return;
    int mid=(l+r)/2;
    if(mid>=k) update(l,mid,T[x].l,T[y].l,k);
    else update(mid+1,r,T[x].r,T[y].r,k);
}

int query(int l,int r,int x,int y,int k){
    if(l==r)
        return l;
    int mid=(l+r)/2;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    if(sum>=k) return query(l,mid,T[x].l,T[y].l,k);
    else return query(mid+1,r,T[x].r,T[y].r,k-sum);
}

int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        cnt=0;
        for(int i=1;i<=n;i++)
            cin>>a[i],v.push_back(a[i]);
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        for(int i=1;i<=n;i++)
            update(1,n,root[i],root[i-1],getid(a[i]));
        int l,r,k;
        while(m--){
            cin>>l>>r>>k;
            cout << v[query(1,n,root[l-1],root[r],k)-1] << endl;
        }
    }
    return 0;
}