Talk is Cheap, Show Me the Code!

0%

区间统计

Posted on Edited on In

给定一个1到n的排列A数组，有m个询问，每次查询下标在[L,R]范围内，小于等于x的数的个数。

输入描述:

第一行2个整数n和m。
第二行n个整数，表示一个排列。
接下来m行，每行3个整数L,R,x。

输出描述:

对于每个询问，输出相应的结果

示例1
输入

5 3
4 3 2 5 1
1 2 3
2 4 3
3 5 4

输出

1
2
2

说明

n,m<=10^5

qujiantongji_fenkuai.cppview raw
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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, m;
const int N = 100010;
int A[N], B[N];
int S;

int query(int L, int R, int x) {
    int ka = L / S, kb = R / S;
    int res = 0;
    if (ka == kb) {
        for (int i = L; i <= R; i++) {
            res += A[i] <= x;
        }
    } else {
        for (int i = L; i < (ka + 1) * S; i++)
            res += A[i] <= x;

        for (int i = ka + 1; i < kb; i++) {
            res += upper_bound(B + i * S, B + i * S + S, x) - (B + i * S);
        }

        for (int i = kb * S; i <= R; i++)
            res += A[i] <= x;
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) {
        scanf("%d", &A[i]);
        B[i] = A[i];
    }
    S = sqrt(n*log(n)/log(2));

    for(int i=S;i+S-1<=n;i+=S){
        sort(B+i, B+i+S);
    }
    while(m--){
        int a, b, x;
        scanf("%d%d%d", &a, &b, &x);
        int ans = query(a, b, x);
        printf("%d\n", ans);
    }
    return 0;
}
qujiantongji2.cppview raw
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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, m;
const int N = 100010;
int A[N], sum[320][N];
int S;

int query(int L, int R, int x) {
    int ka = L / S, kb = R / S;
    int res = 0;
    if (ka == kb) {
        for (int i = L; i <= R; i++) {
            res += A[i] <= x;
        }
    } else {
        for (int i = L; i < (ka + 1) * S; i++)
            res += A[i] <= x;

        for (int i = ka + 1; i < kb; i++) {
            res += sum[i][x];
        }

        for (int i = kb * S; i <= R; i++)
            res += A[i] <= x;
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &m);
    S = sqrt(n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &A[i]);
        sum[i/S][A[i]] ++;
    }


    for(int i=1;i<=n/S; i++)
        for(int j=1;j<=n;j++)
            sum[i][j] += sum[i][j-1];

    while(m--){
        int a, b, x;
        scanf("%d%d%d", &a, &b, &x);
        int ans = query(a, b, x);
        printf("%d\n", ans);
    }
    return 0;
}
qujiantongji_fenwick_tree.cppview raw
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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100010;

int n, m;
int A[N];
int C[N];
int pre[N];
int ans[N];

struct Node{
    int x, id, flag;
};

vector<Node>query[N];

void add(int x, int a){
    while(x<=n){
        C[x] += a;
        x += x&-x;
    }
}

int sum(int x){
    int res = 0;
    while(x){
        res+= C[x];
        x-= x&-x;
    }
    return res;
}


void init(){
    for(int i=1;i<=n;i++) pre[i] = pre[i-1] + A[i];
    for(int i=1;i<=n;i++)
        C[i] = pre[i] - pre[i-(i&-i)];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%d", &A[i]);
    }

    for(int i=1;i<=m;i++){
        int L, R, x;
        scanf("%d%d%d", &L, &R, &x);
        query[R].push_back((Node){x, i, 1});
        query[L-1].push_back((Node){x, i, -1});
    }

//    for(int i=1;i<=n;i++) add(A[i], 1);  wrong
//  下标有序，按序点亮二进制值， 权值树状数组
    for(int i=1;i<=n;i++){
        add(A[i], 1);
        for(int j=0;j<query[i].size();j++){
            ans[query[i][j].id] += query[i][j].flag * sum(query[i][j].x);
        }
    }

//    离线回答询问,
    for(int i=1;i<=m;i++)
        printf("%d\n", ans[i]);
    return 0;
}