专门设计网站的公司叫什么,文化传播公司做网站宣传好吗,花店网页设计模板,柚子皮 wordpress1265. 数星星 - AcWing题库
分析#xff1a;
星星是按纵坐标递增给我们的#xff0c;如果纵坐标相同#xff0c;就按横坐标来给
所以星星是从低到高#xff0c;一行一行来给的
题目要求我们去求每个等级的星星各有多少个
星星的等级由它左下角#xff08;包括左边和下…1265. 数星星 - AcWing题库
分析
星星是按纵坐标递增给我们的如果纵坐标相同就按横坐标来给
所以星星是从低到高一行一行来给的
题目要求我们去求每个等级的星星各有多少个
星星的等级由它左下角包括左边和下边的星星个数来决定的 我们来抽象一下他的操作是什么
1️⃣在某个位置上A[i]1
2️⃣求A1 ~ Ax的前缀和
观察到一个边插入边求前缀和的数据结构想到了树状数组 #include iostream
#include cstring
#include algorithm
#include cstdiousing namespace std;const int N 32010;int n;
int tr[N],level[N];//树状数组三个基本操作
int lowbit(int x) {return x -x;
}int add(int x) {for(int i x;i N;i lowbit(i)) tr[i] ;
}int sum(int x) {int res 0;for (int i x;i;i - lowbit(i)) res tr[i];return res;
}int main () {scanf(%d,n);for (int i 0;i n;i) {int x,y;scanf(%d%d,x,y);x; // 0≤x 树状数组下标一定要从1开始 所以所有星星向右移一个单位 //在添加星星之前先查询否则需要在查询后减去自己 比较麻烦level[sum(x)];//表示该等级的星星增加一个add(x);}for (int i 0;i n;i) {printf(%d\n,level[i]);}return 0;}
如果在查询前先添加则等级都会加1
#include iostream
#include cstring
#include algorithm
#include cstdiousing namespace std;const int N 32010;int n;
int tr[N],level[N];//树状数组三个基本操作
int lowbit(int x) {return x -x;
}int add(int x) {for(int i x;i N;i lowbit(i)) tr[i] ;
}int sum(int x) {int res 0;for (int i x;i;i - lowbit(i)) res tr[i];return res;
}int main () {scanf(%d,n);for (int i 0;i n;i) {int x,y;scanf(%d%d,x,y);x; add(x);level[sum(x)];//表示该等级1的星星增加一个}for (int i 1;i n1;i) {printf(%d\n,level[i]);}return 0;}
