算法|题解

计蒜客 – 棋子等级

凝神长老 · 2月14日 · 2020年 · · 742次已读

计蒜客 棋子等级

假定棋子的等级是左下方的棋子个数,现在给出若干棋子的位置,求不同等级的棋子各有多少个。

输入格式
第一行一个整数 $N (1\leq N\leq 100000)$
接下来 $N$ 行,一行两个整数 $X,Y (0\leq X, Y < 100000)$,表示坐标。
数据保证坐标先按 $Y$ 排序,再按 $X$ 排序。

5
1 1
5 1
7 1
3 3
5 5

输出格式
$N$ 行,每行一个整数,从 $0$ 到 $N−1$ 等级的棋子数量。

1
2
1
1
0

因为题目保证了输入数据的顺序,所以这题就变成了裸的树状数组。
为什么这么说呢?
当我们遇到一个点 (x, y) 的时候,由于题目保证了先按 Y 排序再按 X 排序,所以在 (x, y) 左下角的点一定都遇到过,之后的点都不可能在 (x, y) 左下角,并且,之前遇到的点都是在 (x, y) 左下角的,没有在 (x, y) 其他方位的。
这样一来,如果遇到一个点 (x, y) 的时候,getSum(x) 就会得到$\sum_{i=1}^{x}{C_i}$的和,即树状数组中从 1 开始到 x 的累加值。
可以令每次 change() 的值为 1,这样 sum() 的结果就变成了计数,即出现在 x 之前的点的个数,这个个数就是所求的棋子等级。
只需要在对应棋子等级的计数器上加 1。

ans[getSum(x)]++; // 这个棋子左下的棋子个数是 getSum(x),则对应该等级的棋子个数加 1
change(x); // 把棋子放在这个位置

完整代码如下:

#include <bits/stdc++.h>

using namespace std;

int n = 0;
const int MAX_N = 100007;
int C[MAX_N] = {0};

int lowBit(int x) {
    return x & -x; // return x & (x ^ (x - 1))
}

int getSum(int x) {
    int res = 0;
    while (x != 0) {
        res += C[x];
        x -= lowBit(x);
    }
    return res;
}

void change(int x) {
    while (x <= MAX_N) {
        C[x]++;
        x += lowBit(x);
    }
}

int main() {
    scanf("%d", &n);
    int ans[n];

    for (int i = 0; i < n; i++) {
        ans[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        x++; // 树状数组的下标从 1 开始
        ans[getSum(x)]++; // 这个棋子左下的棋子个数是 getSum(x),则对应该等级的棋子个数加 1
        change(x); // 把棋子放在这个位置
    }

    for (int a: ans) {
        printf("%d\n", a);
    }

    return 0;
}
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论