蓝桥杯真题——数星星

输入样例：

5
1 1
5 1
7 1
3 3
5 5

输出样例：

1
2
1
1
0

分析：

根据题目，是逐行读入数据，我们要求每颗星星左下方的星星数量，就是要迅速求一个区间内的值

于是我们联想到树状数组来解决问题

代码演示：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;const int N = 15010,M = N*2;
int n;
int tr[M],level[N];// 树状数组的基本三个函数 
int lowbit(int x)
{return x&-x;
}// 寻找前驱结点，快速得到前缀和 
int query(int x)
{int res = 0;for(int i=x;i;i-=lowbit(i)){res+=tr[i];}return res;
}// 改变某一个数的值，要将祖先也改变 
void add(int x,int v)
{for(int i=x;i<M;i+=lowbit(i))tr[i]+=v;return;
}int main(void)
{scanf("%d",&n);for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);// lowbit(0)=0会导致死循环// 要将所有坐标向右平移一个点位,不影响 x++;// 看前面有没有存储的值 int t = query(x);// 星星值 level[t]++;// 构造树状数组 add(x,1);}for(int i=0;i<n;i++){scanf("%d\n",level[i]);}return 0;
}

感谢查看！