前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十三讲：树状数组与线段树【习题】
本篇博客所包含习题有：
👊小朋友排队
👊油漆面积
树状数组与线段树【例题】见博客：蓝桥杯第十三讲–树状数组与线段树【例题】
注： 蓝桥杯对于树状数组与线段树的考察十分的基础简单，且历年只考察过两道题目，读者不需要了解其原理，只需要背诵模板学会调用即可。如果想要知道具体实现方式，见博客：树状数组，线段树（一），线段树（二） 【尚未更新】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
小朋友排队
来源： 第五届蓝桥杯省赛C++B/C组
题目要求
题目描述：
n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1 ，如果第二次要求他交换，则他的不高兴程度增加 2 （即不高兴程度为 3 ），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k 。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式：
输出格式：
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
数据范围：
输入样例：
3 3 2 1
输出样例：
9
样例解释：
首先交换身高为 3 和 2 的小朋友，再交换身高为 3 和 1 的小朋友，再交换身高为 2 和 1 的小朋友，每个小朋友的不高兴程度都是 3 ，总和为 9。
思路分析
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 1000010; int n; int h[N], tr[N]; int sum[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i < N; i += lowbit(i)) tr[i] += v; } 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 = 0; i < n; i ++ ) scanf("%d", &h[i]), h[i] ++; // 求前面有多少个数比它大 for (int i = 0; i < n; i ++ ) { sum[i] = query(N - 1) - query(h[i]); add(h[i], 1); } // 求后面有多少个数比它小 memset(tr, 0, sizeof tr); for (int i = n - 1; ~i; i -- ) { sum[i] += query(h[i] - 1); add(h[i], 1); } LL res = 0; for (int i = 0; i < n; i ++ ) res += (LL)sum[i] * (sum[i] + 1) / 2; printf("%lld\n", res); return 0; }
油漆面积
来源： 第八届蓝桥杯省赛C++A组,第八届蓝桥杯省赛JAVAA组
题目要求
题目描述：
输入格式：
输出格式：
一行一个整数，表示矩形覆盖的总面积。
数据范围：
输入样例1：
3 1 5 10 10 3 1 20 20 2 7 15 17
输出样例1：
340
输入样例2：
3 5 2 10 6 2 7 12 10 8 1 15 15
输出样例2：
128
思路分析
蓝桥杯历史上唯一一次考过的线段树的题目。本题求法如下图所示，用扫描线进行优化：
即我们在计算面积的时候有：
代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 10010; int n; struct Segment { int x, y1, y2; int k; bool operator< (const Segment &t)const { return x < t.x; } }seg[N * 2]; struct Node { int l, r; int cnt, len; }tr[N * 4]; void pushup(int u) { if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1; else if (tr[u].l == tr[u].r) tr[u].len = 0; else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; } void build(int u, int l, int r) { tr[u] = {l, r}; if (l == r) return; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); } void modify(int u, int l, int r, int k) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].cnt += k; pushup(u); } else { int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) modify(u << 1, l, r, k); if (r > mid) modify(u << 1 | 1, l, r, k); pushup(u); } } int main() { scanf("%d", &n); int m = 0; for (int i = 0; i < n; i ++ ) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); seg[m ++ ] = {x1, y1, y2, 1}; seg[m ++ ] = {x2, y1, y2, -1}; } sort(seg, seg + m); build(1, 0, 10000); int res = 0; for (int i = 0; i < m; i ++ ) { if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x); modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k); } printf("%d\n", res); return 0; }
