本文主要是介绍蓝桥杯刷题-数星星,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1265. 数星星 - AcWing题库
/* 题目中的y是递增,不影响 */
/* 直接看作一维数组的更新维护 */
/* 将数据二进制化,拿最低位的1 */
/* 转化为线段树的解法才是核心 */
/* 思想是前缀和 */
#include <bits/stdc++.h>using namespace std;const int N = 15010 , M = 32010;int level[M];
int tr[M];
int n;
/* 求最低位的1 */
int lowbit(int x)
{return x&-x;
}
/* 树状数组 */
int add(int x, int v)
{for(int i = x;i <= M;i += lowbit(i)) tr[i] += v;
}
/* 查询 */
int qy(int x)
{int ans = 0;for(int i = x; i ;i -= lowbit(i)){ans += tr[i];}return ans;
}int main()
{/* 读入 */cin >> n;for(int i = 0;i < n;i ++){int x , y;cin >> x >> y;x ++; //防止出现0的情况level[qy(x)] ++; // 前缀和结果add(x ,1);}for(int i = 0;i < n;i ++) cout << level[i] << endl;return 0;
}
这篇关于蓝桥杯刷题-数星星的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!