hdu 4417 Super Mario （树状数组）

109 阅读 0 评论 72 点赞

我是靠谱客的博主长情小刺猬，这篇文章主要介绍hdu 4417 Super Mario （树状数组），现在分享给大家，希望可以做个参考。

思路：对n个数用结构体数组保存，记录值和次序id

复制代码

1
2
3
struct node{
    int num,id;
}a[MAX_];

对m个查询用结构体数组保存，记录左右(L,R)及H以及次序id

复制代码

1
2
3
struct point {
    int L,R,id,value;
}b[MAX_];

以num值从小到大排序，以value值从小到大排序。

然后从排好序的第一个询问和排好序的num值的第一个开始，若是小于第一个询问的value的num，则将其id全部放入树状数组，直到大于该value值时

复制代码

1
2
3
4
5
6
7
for(int q = 0, k = 0; q < m; ++q){
     while(k < n && b[q].value >= a[k].num){
        add(a[k].id,1);
        k++;
     }
     ans[b[q].id] = sum(b[q].R) - sum(b[q].L-1);
}

此时即可用树状数组的求和函数根据该value对应的(L,R)求得该查询的answer了。然后继续第二个查询，因为之后的value都是越来越大，所以之前加入的都是符合要求的，num只要一直往后数即可。

原理即是离散化，然后对id进行树状数组，保证了不会影响后续的值的正确性，又保证了时间复杂度，很是巧妙

代码：

复制代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 100010;
const int INF = 0x7fffffff;
const int MAX = 100010;

struct point {
    int L,R,id,value;
} b[MAX_];

struct node {
    int num,id;
} a[MAX_];

int C[MAX_], ans[MAX_];
int T, n, m,l ,r;

int lowbit(int x) {
    return x&(-x);
}

void add(int x,int num) {
    while(x < MAX) {
        C[x] += num;
        x += lowbit(x);
    }
}

int sum(int x) {
    int cnt = 0;
    while(x > 0) {
        cnt += C[x];
        x -= lowbit(x);
    }
    return cnt;
}

bool cmp1(const point &a, const point &b) {
    return a.value < b.value;
}

bool cmp2(const node &a,const node& b) {
    return a.num < b.num;
}

int main() {
    int Case = 0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++i) {
            scanf("%d",&a[i].num);
            a[i].id = i+1;
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d%d",&l,&r,&b[i].value);
            b[i].L = l + 1;
            b[i].R = r + 1;
            b[i].id = i ;
        }
        sort(a,a+n,cmp2);
        sort(b,b+m,cmp1);
        mst(C,0);
        mst(ans,0);

for(int q = 0, k = 0; q < m; ++q) {
            while(k < n && b[q].value >= a[k].num) {
                add(a[k].id,1);
                k++;
            }
            ans[b[q].id] = sum(b[q].R) - sum(b[q].L-1);
        }
        printf("Case %d:n",++Case);
        for(int i = 0; i < m; ++i) {
            printf("%dn",ans[i]);
        }

}
    return 0;
}

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 100010;
const int INF = 0x7fffffff;
const int MAX = 100010;

struct point {
    int L,R,id,value;
} b[MAX_];

struct node {
    int num,id;
} a[MAX_];


int C[MAX_], ans[MAX_];
int T, n, m,l ,r;


int lowbit(int x) {
    return x&(-x);
}

void add(int x,int num) {
    while(x < MAX) {
        C[x] += num;
        x += lowbit(x);
    }
}

int sum(int x) {
    int cnt = 0;
    while(x > 0) {
        cnt += C[x];
        x -= lowbit(x);
    }
    return cnt;
}

bool cmp1(const point &a, const point &b) {
    return a.value < b.value;
}

bool cmp2(const node &a,const node& b) {
    return a.num < b.num;
}

int main() {
    int Case = 0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++i) {
            scanf("%d",&a[i].num);
            a[i].id = i+1;
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d%d",&l,&r,&b[i].value);
            b[i].L = l + 1;
            b[i].R = r + 1;
            b[i].id = i ;
        }
        sort(a,a+n,cmp2);
        sort(b,b+m,cmp1);
        mst(C,0);
        mst(ans,0);

        for(int q = 0, k = 0; q < m; ++q) {
            while(k < n && b[q].value >= a[k].num) {
                add(a[k].id,1);
                k++;
            }
            ans[b[q].id] = sum(b[q].R) - sum(b[q].L-1);
        }
        printf("Case %d:n",++Case);
        for(int i = 0; i < m; ++i) {
            printf("%dn",ans[i]);
        }

    }
    return 0;
}