数星星
题目要求
题目描述：
输入格式：
输出格式：
N 行，每行一个整数，分别是 0 级，1 级，2 级，……，N − 1 级的星星的数目。
数据范围：
1≤N≤15000,
0≤x,y≤32000
输入样例：
5 1 1 5 1 7 1 3 3 5 5
输出样例：
1 2 1 1 0
思路分析
对于一颗星星的等级是查看这个星星的下方和左方有多少颗星星，因为我们的输入是从下到上，从左到右进行输入的，所以我们在对于每一颗星星进行统计的时候，可以边输入边计算，因为这样我们就只需要考虑横坐标的星星，即对于一颗横坐标为 x 的星星，我们在输入它后，只需要查看一下从位置 1 ~ x （树状数组要求从 1开始，但是我们的数据范围可以取到 0 ，故我们直接让 x ++; 即可）有多少颗星星即可，这样就转化为了一个求前缀和的问题，因为整个前缀和的过程是动态的，所以我们使用树状数组进行优化，因为我们的代码思路是边输入边进行统计，这样构造线段树的话会有些麻烦，故本题建议使用树状数组而不是线段树。level[i] 表示的就是等级为 i ii 的星星的个数。
代码
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N = 32010; int n; int tr[N], level[N]; int lowbit(int x) { return x & -x; } void add(int x) { for (int i = x; i < N; i += lowbit(i)) tr[i] ++; } int query(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 = 1; i <= n; i ++ ) { int x, y; scanf("%d%d", &x, &y); x ++; level[query(x)] ++; add(x); } for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]); return 0; }
数列区间最大值
题目要求
题目描述：
输入一串数字，给你 M 个询问，每次询问就给你两个数字 X , Y 要求你说出 X 到 Y 这段区间内的最大数。
输入格式：
第一行两个整数 N , M 表示数字的个数和要询问的次数；
接下来一行为 N 个数；
接下来 M 行，每行都有两个整数 X , Y。
输出格式：
输出共 M 行，每行输出一个数。
数据范围：
输入样例：
10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8
输出样例：
5 8
思路分析
本题求的是最大值，和前缀和无关，即我们用树状数组无法解决问题，那么我们就可以使用线段树去解决本题，代码和本博客的第一道例题：动态求连续区间和 是类似的，只需要对求和部分改成求最大值就可以了，其中代码中出现了：INT_MIN，这代表的是整数的最小值，即极小值，调用该函数需要加头文件：#include <climits>
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> using namespace std; const int N = 100010; int n, m; int w[N]; struct Node { int l, r; int maxv; }tr[4 * N]; void pushup(int u) { tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv); } void build(int u, int l, int r) { if (l == r) tr[u] = {l ,r, w[l]}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv; int mid = tr[u].l + tr[u].r >> 1; int maxv = INT_MIN; if (l <= mid) maxv = max(maxv, query(u << 1, l ,r)); if (r > mid) maxv = max(maxv, query(u << 1 | 1, l, r)); return maxv; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); build(1, 1, n); int l, r; while (m -- ) { scanf("%d%d", &l, &r); printf("%d\n", query(1, l, r)); } return 0; }
