本文写于 2020年02月14日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

计蒜客 棋子等级

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

输入格式
第一行一个整数 $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;
}
0 0 投票数
评分
发表留言
订阅评论
提醒
guest

在点击发表评论按钮时,网络请求的数据包含浏览器版本、操作系统版本和 IP 地址;您的网络服务提供商、雇主或学校、政府机构可能会看到您的访问活动;根据浏览器默认行为、操作系统设置和安全防护软件的设置不同,您的浏览器可能会也可能不会在本地 Cookies 缓存您输入的用户名、邮箱以便下次评论使用。

请对自己的言行负责。

您想以什么身份发表评论
邮箱将在您的评论被回复时给您通知
(可选)如果您也有个人网站,不妨分享一下
我对这篇文章的评分
这篇文章给您带来多大帮助
0 评论
内联反馈
查看所有评论