区间最值
title: 题目
在学校的入口处有一个巨大的矩形广告牌，高为h，宽为w。所有种类的广告都可以贴，比如ACM的广告啊，还有餐厅新出了哪些好吃的，等等。。
在9月1号这天，广告牌是空的，之后广告会被一条一条的依次贴上去。
每张广告都是高度为1宽度为wi的细长的矩形纸条。
贴广告的人总是会优先选择最上面的位置来帖，而且在所有最上面的可能位置中，他会选择最左面的位置，而且不能把已经贴好的广告盖住。
如果没有合适的位置了，那么这张广告就不会被贴了。
现在已知广告牌的尺寸和每张广告的尺寸，求每张广告被贴在的行编号。
多组样例，不超过40个。
对每组样例，第一行包含3个整数h，w，n(1 <= h,w <= 10^9; 1 <= n <= 200,000) -广告牌的尺寸和广告的个数。 下面n行每行一个整数 wi (1 <= wi <= 10^9) - 第i张广告的宽度
对每张广告，输出它被贴在的行编号（是1到h之间的数），顶部是第一行。如果某广告不能被贴上，则输出-1。 title: input 3 5 5 2 4 3 3 3 title: output 1 2 1 3 -1 title: 思路 给你的广告高度都是1, 故可以将广告牌的高度看做数组下标, 宽度为数组值, 一个广告放到数组1位置上时,就将其值减去广告宽度, 直到没法再加。
不能使用数组来模拟这个过程, 每次加时得从头往后找。
使用线段树, 记录区间的最大值, 这样如果这个区间的最大值都小于广告宽度, 就不再查找, 往另一个区间查找, 直到找到一个点。
找不到则输出-1即可 title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2e5 + 10, M = 4 * N; typedef long long ll; int tree[M]; int h, w, n;
int readInt() { int t; scanf("%d", &t); return t; }
void ps(int node) { tree[node] = max(tree[node << 1], tree[node << 1 | 1]); }
void build(int node, int L, int R) { if (L == R) { tree[node] = w; return; } int mid = L + R >> 1; build(node << 1, L, mid), build(node << 1 | 1, mid + 1, R); ps(node); }
int query(int node, int L, int R, int value) { if (L == R) { tree[node] -= value; return L; } int mid = L + R >> 1; int res = 0; if (tree[node << 1] >= value) res = query(node << 1, L, mid, value); else if (tree[node << 1 | 1] >= value) res = query(node << 1 | 1, mid + 1, R, value); ps(node); return res; }
int main() { while (scanf("%d %d %d", &h, &w, &n) == 3) { h = min(h, n); build(1, 1, h); while (n--) { int t = readInt(); if (t > tree[1]) printf("-1\n"); else printf("%d\n", query(1, 1, h, t)); for (int i = 1; i <= h + 2; i++) cout << tree[i] << " "; cout << endl; } } } ~~~ 区间更新+区间查询
title: 题目 給定 N, Q，代表序列有 N 個元素，他們的初始值皆是 1。 接下來 Q 行，每行有三個數字 X, Y, Z，代表將序列中 X 到 Y 的元素值改成 Z。 最後輸出序列元素的和。
多組測資，第一個數字 T 代表有幾組測資。 對於每一組測資，第一行會輸入一個數字 N (1<=N<=100,000)，下一行會輸入一個數字 Q (0<=Q<=100,000)。 接下來 Q 行，每行有三個數字 X, Y, Z (1<=X<=Y<=N, 1<=Z<=3)
對於每一筆測資，輸出一個數字代表序列每個元素的總和，格式請參考範例輸出 title: input 1 10 2 1 5 2 5 9 3 title: output Case 1: The total value of the hook is 24. title: 思路
直接用线段树模拟更新该节点即其所有子节点会超时。 使用lazy技巧, 若更新到 `[0,5]` 节点时, 就在该节点打上一个`lazy = Z`的标记, 同时停止向下继续更新, 直接返回。 等到某一次又更新到 `[0,5]` 节点时, 且不是最终要找的节点, 说明需要用到该节点之后的节点, 那么就需要将上次存的lacy更新到直系子节点, 同样也不必一次更新全部子节点, 只更新自己的直系两个就行, 这两个用到那个后面会再次进行这个过程。
就这样可以优化很多时间复杂度。 title:代码 ~~~ c ++ #include <cstring> #include <cstdio> #include <algorithm> using namespace std; #define lson l, mid, u << 1 #define rson mid + 1, r, u << 1 | 1 #define MID l + r >> 1 const int N = 1e5 + 10; int readInt() { int t; scanf("%d", &t); return t; }
struct node { int l, r; int val, lazy; } t[N << 2];
void pushup(int u) { t[u].val = t[u << 1].val + t[u << 1 | 1].val; }
void build(int l, int r, int u = 1) { t[u] = {l, r, 1, 0}; if (l == r) return; int mid = MID; build(lson), build(rson); pushup(u); }
void pushdown(node &op, int lazy) { op.val = lazy * (op.r - op.l + 1); op.lazy = lazy; }
void pushdown(int u) { if (!t[u].lazy) return; pushdown(t[u << 1], t[u].lazy); pushdown(t[u << 1 | 1], t[u].lazy); t[u].lazy = 0; }
void modify(int l, int r, int c, int u = 1) { if (l <= t[u].l && r >= t[u].r) // 当节点在所需区间内 { pushdown(t[u], c); // 更新该节点的总和, 且置lazy为更新值 return; } pushdown(u); // 此时所需区间在该节点里面, 即需要用到该节点的子节点, 则去清除该节点的lazy, 让子节点的值加上lazy // 注意也不是把下面所有子节点全给更新, 只更新直系子节点, 后面用到会重复这个操作 int mid = t[u].l + t[u].r >> 1; if (l <= mid) modify(l, r, c, u << 1); if (r > mid) modify(l, r, c, u << 1 | 1); pushup(u); }
int main() { int T = readInt(); for (int kase = 1; kase <= T; kase++) { int n = readInt(), m = readInt(); build(1, n); while (m--) // l, r, c { int l, r, c; scanf("%d %d %d", &l, &r, &c); modify(l, r, c); } printf("Case %d: The total value of the hook is %d.\n", kase, t[1].val); } return 0; } ~~~ 求逆序对
title: 题目 给一个序列，我们使用冒泡排序法对它进行排序。请输出在排序过程中会进行多少次交换。
输入包含多个测试用例
每个测试用例第一行为一个整数n（n<500000）表示数组的长度 下面n行每一行包含一个整数0≤a[i]≤999,999,999，即数组中第i个元素的值。
当n=0时结束输入
对于每个输入序列，程序打印一个数op，即对给定输入序列进行排序所需的最小交换操作数。 title: input 5 9 1 0 5 4 3 1 2 3 0 title: output 6 0 title: 思路
冒泡排序是$n^2$的, 这里不能用冒泡模拟, 可以试试快排和归并。
冒泡的最小交换数就是它交换的总次数, 也就说出现 后面的数大于前面的数就算一次交换。 显然这就是求逆序对的数量, 归并可以解决： ~~~ c ++ int merge_sort(int q[], int l, int r) { if(l >= r) return 0; int mid = l +r >> 1; int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); int i = l, j = mid + 1, k = l; while(i <= mid &&j <= r) if(a[i] <= a[j]) temp[k++] = a[i++]; else { temp[k++] = a[j]; res += j - k; } while(i <= mid) temp[k++] = a[i++]; while(j <= r) temp[k++] = a[j++]; for(i; i <= r; i++) a[i] = temp[i]; return res; } ~~~
换一种写法, 怎么用线段树来写呢？ 当前数x, 后面任何一个大于x的都是逆序对, 即找在 x 后面 >= x的数 的数量。 先将输入的数组排序（这里就已经慢于归并写法, 图一乐）, 然后记录原数组每个元素排序后的位置。 使用线段树的 upadate 操作依次按原数组顺序插入, 但插入的位置是排序后的位置。 即 第一个插入 9 (排序后位置pos = 5), 就插入到 [5,5], 值为该位置被插入的次数。 线段树权值记录为左右子树的和。 因为插入位置是排序后的位置, 故插入到右子树的原值肯定比插入到左子树的原值大（或者等于）,所以如果插入到左子树时, 右子树有值, res就去加上右子树的值。 对于等于的情况, 可以在开始求pos时就将其化到一个位置。
如果数据范围小的话可以直接将插入的位置变成数值, 即 9 就插入到 [9,9], 省去排序操作。 title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <queue> #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int N = 3e6 + 10;
int t[N], a[N]; int n; vector<int> vec;
void update(int l, int r, int u, int idx, int val, long long &res) { if (l == r) { t[u]++; return; } int mid = l + r >> 1; if (idx <= mid) { update(l, mid, u << 1, idx, val, res); res += t[u << 1 | 1]; } else update(mid + 1, r, u << 1 | 1, idx, val, res); t[u] = t[u << 1] + t[u << 1 | 1]; }
int main() { ios::sync_with_stdio(false); cin.tie(0); while (cin >> n && n != 0) { memset(t, 0, sizeof t); memset(a, 0, sizeof a); vec.clear(); for (int i = 1; i <= n; i++) { cin >> a[i]; vec.push_back(a[i]); } sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end());
int pos; long long res = 0; for (int i = 1; i <= n; i++) { pos = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1; // cout << pos << " "; update(1, n, 1, pos, a[i], res); } cout << res << endl; } return 0; } ~~~ title: 题目 给定数列 a1, a2, ..., an 的倒数是满足 i < j 和 ai > aj 的对 (ai, aj) 的个数。 对于给定的数字序列 a1, a2, ..., an，如果我们将前 m 个数字(m>=0)移动到序列的末尾，我们将获得另一个序列。总共有 n 个这样的序列，如下所示： a1, a2, ..., an-1, an（其中 m = 0 ） a2, a3, ..., an, a1（其中 m = 1） a3, a4, ..., an, a1, a2（其中 m = 2） ... an, a1, a2, ..., an-1（其中 m = n-1） 你被要求编写一个程序，从上述序列中找出最小的倒数。
输入由多组测试用例组成。每个案例由两行组成：第一行包含一个正整数 n (n <= 5000)；下一行包含从 0 到 n-1 的 n 个整数的排列。
对于每种情况，在一行上输出最小倒数。 title: input 10 1 3 6 9 0 8 5 7 4 2 title: output 16 title: 思路
title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <queue> #include <cstdio>
using namespace std; const int N = 5e3 + 10; int a[N], b[N], temp[N]; int n; int merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; int res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) if (a[i] <= a[j]) temp[k++] = a[i++]; else { res += mid - i + 1; temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <= r) temp[k++] = a[j++];
for (i = l, j = 0; i <= r; i++, j++) a[i] = temp[j]; return res; }
int main() { while (cin >> n) { for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = a[i]; } /* for (int k = 0; k < n; k++) cout << b[k] << " "; cout << endl;*/ int res = merge_sort(0, n - 1); for (int i = 0; i < n - 1; i++) { for (int j = i + 1, k = 0; j != i; j++, j %= n, k++) a[k] = b[j]; a[n - 1] = b[i]; /* for (int k = 0; k < n; k++) cout << a[k] << " "; cout << endl;*/ res = min(res, merge_sort(0, n - 1)); } cout << res << endl; }
return 0; } ~~~ title: 题目 农夫约翰的牛发现，他的田地里沿着山脊生长的三叶草（我们可以将其视为一维数字线）特别好。
农夫约翰有N头母牛（我们将母牛的编号从1到N）。每位农夫约翰的N头母牛都有她特别喜欢的三叶草范围（这些范围可能重叠）。范围由闭合间隔[S，E]定义。
但是有些母牛很强壮，有些却很弱。给定两个母牛：母牛i和母牛j，它们最喜欢的三叶草范围是[Si，Ei]和[Sj，Ej]。如果Si <= Sj并且Ej <= Ei并且Ei-Si> Ej-Sj，我们说母牛i比母牛j强。
对于每头母牛，有几头母牛比她强？农夫约翰需要您的帮助！
输入项
输入包含多个测试用例。
对于每个测试用例，第一行是整数N（1 <= N <= 10 ^ 5），它是母牛的数量。然后是N行，其第i行包含两个整数：S和E（0 <= S
输入的末尾包含单个0。
输出量
对于每个测试用例，输出一行包含n个以空格分隔的整数，其中第i个数字指定比母牛i强的母牛的数量。 title: input 3 1 2 0 3 3 4 0 title: output 1 0 0 title: 思路
就是求一个区间是多少个区间的子区间, 且不能相等。 区间问题自然先想到排序, 我们按照右端点从大到小排序, 对于任何一个区间 i : `range[i].r >= range[i - 1].r` 那么只需要找到 `[1, i)` 之间 所有 `左端点 < range[i].l` 的区间数量, 就是该区间的子区间总数。
那么如何找到一个乱序数组中所有 <= x的数量呢？ 注意到该题区间数值 <= $10^5$, 也就是说我们可以用一个bool数组来代表所有数。 然后使用线段树/树状数组来求这个和。
也可以再进行右端点的排序, 然后二分找到位置。
这里使用树状数组来实现这个操作。 title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <queue> #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> PII; int readInt() { int t; scanf("%d", &t); return t; }
//------- Coding Area ---------// const int N = 1e5 + 10; int n; int t[N]; int res[N]; struct Range { int l, r; int id;
} range[N];
inline bool cmp(const Range &a, const Range &b) { if (a.r == b.r) return a.l < b.l; return a.r > b.r; }
int lowbit(int x) { return x & -x; }
void add(int i) { for (i; i <= n; i += lowbit(i)) t[i] += 1; }
int sum(int i) { int sum = 0; for (i; i; i -= lowbit(i)) sum += t[i]; return sum; }
int main() { ios::sync_with_stdio(false); cin.tie(0);
while (cin >> n && n) { memset(t, 0, sizeof t); for (int i = 1; i <= n; i++) { cin >> range[i].l >> range[i].r; range[i].l += 1; range[i].r += 1; range[i].id = i; }
sort(range + 1, range + 1 + n, cmp);
for (int i = 1; i <= n; i++) { int j = range[i].id; if (i > 1 && range[i].l == range[i - 1].l && range[i].r == range[i - 1].r) res[j] = res[range[i - 1].id]; else res[j] = sum(range[i].l); add(range[i].l); }
for (int i = 1; i <= n; i++) cout << res[i] << " "; cout << "\n"; }
return 0; } ~~~ title: 题目 ![[Pasted image 20220802100243.png]] title: input 2 6 1 3 2 6 5 4 5 3 5 2 4 1 title: output Case #1: 10 Case #2: 1 title: 思路 $$ \begin{align*} & a[x] < a[z] < a[y] 且 x < y < z \\
& (x < y < z) \\ & == (x < y < z) + (x < z < y) - (x < z < y)\\ & == (x < *) - (x < z < y)\\ \end{align*} $$ 根据x来找, 找后面比这个数大的个数n, 求 $C^{2}_{n}$ 求 $(x < z < y)$ 则把当前数当做z, 小于z的个数\*大于z的个数即可。
**小于当前数的个数: **`sum1 = sum(a[i]);` **大于当前数的个数：** `(n - a[i]) - (i - 1 - sum1)` 前一项是所有大于当前数的个数, 后一项是之前计算过的大于当前数的个数, 作差即是后面大于该数的个数。 **(x < z < y): ** `大于当前数的个数 \* 小于当前数的个数` **(x < *): ** `大于当前数的个数 * （大于当前数的个数 - 1） / 2`
如何快速求小于当前数的个数？ 用树状数组。 title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <queue> #include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> PII; int readInt() { int t; scanf("%d", &t); return t; }
//------- Coding Area ---------// const int N = 5e5 + 10, MOD = 1e8 + 7; int t[N], a[N], n;
int lowbit(int i) { return i & -i; }
void add(int i) { for (i; i <= n; i += lowbit(i)) t[i]++; }
int sum(int i) { int s = 0; for (i; i; i -= lowbit(i)) s += t[i]; return s; }
int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; for (int kase = 1; kase <= T; kase++) { memset(t, 0, sizeof t); cin >> n; long long res = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; int sum1 = sum(a[i] - 1); // 小于当前数的个数 add(a[i]); int t = (n - a[i]) - (i - sum1 - 1); // 大于当前数的个数 res += (long long)t * (t - 1) / 2 - (long long)sum1 * t; res = (res % MOD + MOD) % MOD; } cout << "Case #" << kase << ": " << res << "\n"; } }
~~~ 区间合并
title: 题目 火山经营着一个停车场，假设的停车场有$N$车位（编号$1-N$）都在一条线上，最初所有车位都没停车。经常有人来定车位，他要定连续的$k(1 ≤ k ≤ N)$个车位。火山要确定是否能够满足客人的要求，如果能，他要将这$k$个连续的车位安排在编号最小的地方停下。若不能，则客人不停在火山的停车场。在某一时间，有些车会被车主开走了。火山的停车场很大，火山想让学弟学妹写个程序帮助他。
第1行输入$N$ 和 $M$。$N$是车位个数，M是停车和开走车操作的总次数
接下来M行，先输入操作类型（1或2） 若是1，表示有人来停车，再输入$k$ 若是2，再输入$l$, $r$,表示区间$[l, l + r)$的车被开走了。
$N (1 ≤ N ≤ 50,000)$ $M (1 ≤ M < 50,000)$
当输入为1时，若火山的停车场有连续的k个车位，那么输出第一辆车停的最小的编号，否则输出0。 title: input 10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 title: output 1 4 7 0 5 title: 思路
线段树记录每个区间的最大连续未停车长度, 叶子节点就是1/0. 父节点则判断左子树的连续区间是否和右子树的连续区间连接, 如果连接则为相加后长度, 若不连接则取最大长度。 用st,ed记录当前区间的最大停车长度会导致区间内两个相同长度的区间只能用其中一个, 对后续的区间合并有很大影响。
正解是储存 `lsum` 从左端点向右的停车长度, `rsum`从右端点向左的停车长度, 至于中间的区间两端都不占则会由 `msum`取代（max_sum), 这个`msum`也可以是`lsum / rsum` 只要他们的长度大于中间长度（因为可以完全代替且还方便合并,中间的区间是永远无法用来合并的）。
**建树**： 默认全空, 则直接将 `lsum = rsum = msum = len(区间长度)` **更新**： 因为是区间更新, 使用**lazy**懒更新来优化时间。（有向上更新pushup和向下更新pushdown） 设当前节点为 `father`, 左子树为 `lson`, 右子树为 `rson`。 - **pushup**： father的lsum, 直接等于 lson的lsum father的rsum, 直接等于 rson的rsum father的msum, 直接等于 lson和rson的 msum 最大值 接下来考虑是否合并区间 若lson的lsum跟它的区间长度相等, 也就是说全部都可以停车, 则`father的lsum = lson.lsum + rson.lsum` 若rson的rsum跟它的区间长度相等, 也就是说全部都可以停车, 则`father的rsum = ron.rsum + lson.rsum` 至于msum, 则在`(lson.msum, rson.msum, lson.rsum + rson.lsum)` 最后一项是中间拼接的结果。 - **pushdown**： 如果`lazy != -1`说明需要下放标记 如果是更新0(可以停)就 `lsum = rsum = msum = len`(左/右子树分别为 `len - len/2` / `len/2`) 如果是更新1(不可以停)就 `lsum = rsum = msum = 0` **查询**： 若根节点的msum都小于k则直接输出0 若大于等于k则 优先往左边找, 左子树也大于等于k则继续找子节点。 直到找到一个节点它的左子树和右子树都小于k, 说明该区间就是要找的区间, 返回`mid - 左子树的rsum + 1` 即是区间最左边的点位置。
代码量很大, 但理清思路就很好写了, 注意规范码风这样不容易出现小错误。 title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <algorithm>
using namespace std;
const int N = 5e4 + 10, M = N << 2; struct Node { int l, r; int lsum, rsum, msum; void set(int val) { lsum = rsum = msum = val; } } t[M]; int lazy[M];
void pushup(int u, int len) { Node &l = t[u << 1], &r = t[u << 1 | 1]; // 用引用简化代码 t[u].lsum = l.lsum, t[u].rsum = r.rsum; // 不考虑合并区间 if (l.lsum == len - (len >> 1)) // 合并区间 t[u].lsum += r.lsum; if (r.rsum == (len >> 1)) t[u].rsum += l.rsum; t[u].msum = max(max(l.msum, r.msum), l.rsum + r.lsum); }
void pushdown(int u, int len) { if (lazy[u] != -1) { Node &l = t[u << 1], &r = t[u << 1 | 1]; lazy[u << 1] = lazy[u << 1 | 1] = lazy[u]; // 标记下放 if (lazy[u]) l.set(0), r.set(0); else l.set(len - (len >> 1)), r.set(len >> 1); lazy[u] = -1; } }
void build(int l, int r, int u = 1) { int len = r - l + 1; // t[u] = {l, r, len, len, len}; // POJ不支持的特性 t[u].l = l, t[u].r = r, t[u].lsum = t[u].rsum = t[u].msum = len; if (l == r) return; int mid = l + r >> 1; build(l, mid, u << 1), build(mid + 1, r, u << 1 | 1); }
void modify(int L, int R, int val, int u = 1) { if (t[u].l >= L && t[u].r <= R) { if (val) t[u].set(0); else t[u].set(t[u].r - t[u].l + 1); lazy[u] = val; return; } pushdown(u, t[u].r - t[u].l + 1); int mid = t[u].l + t[u].r >> 1; if (mid >= L) modify(L, R, val, u << 1); if (R > mid) modify(L, R, val, u << 1 | 1); pushup(u, t[u].r - t[u].l + 1); }
int query(int len, int u = 1) { if (t[u].l == t[u].r) return t[u].l; pushdown(u, t[u].r - t[u].l + 1); int mid = t[u].l + t[u].r >> 1;
if (t[u << 1].msum >= len) return query(len, u << 1); else if (t[u << 1].rsum + t[u << 1 | 1].lsum >= len) // 要找的最小区间 return mid - t[u << 1].rsum + 1; else return query(len, u << 1 | 1); } int main() { cin.tie(0)->sync_with_stdio(false); int n, m; cin >> n >> m; build(1, n); memset(lazy, -1, sizeof lazy); while (m--) { int op; cin >> op; if (op == 1) { cin >> op; if (t[1].msum < op) cout << 0 << "\n"; else { int res = query(op); cout << res << "\n"; modify(res, res + op - 1, 1); } } else { int l, r; cin >> l >> r; modify(l, l + r - 1, 0); } } /* for (int i = 1; i <= n + 2; i++) cout << t[i].lsum << " " << t[i].rsum << " " << t[i].msum << endl; */ return 0; }
~~~ 扫描线离散化线段树
title: 题目 输入包含几个测试用例。每个测试例开始与含有可用映射的单个整数n$（1 <= N <= 100）$的线。 接下来的n行分别描述一张地图。 每条线包含四个数字 $x1; y1; x2; y2x1;y1;x2;y2$ $(0<=x1<x2<=100000;0<=y1<y2<=100000)$，不一定是整数。 值$（x1; y1）$和$（x2; y2）$是左上角的坐标。映射区域的右下角。 输入文件由包含单个0的行终止。请勿对其进行处理。
对于每个测试用例，您的程序应输出一个部分。 每个部分的第一行必须是 Testcase \#k，其中k是测试用例的编号（从1开始）。 第二个必须是Total explored area: a，其中a是总探索区（即此测试用例中所有矩形的并集面积），精确打印到小数点右边的两位数。 在每个测试用例之后输出空白行。 title: input 2 10 10 20 20 15 15 25 25.5 0 title: output Test case #1 Total explored area: 180.00 title: 思路 **有大佬制作[视频讲解](https://www.bilibili.com/video/BV1yo4y197Zd?share_source=copy_pc)** 不过有些细节没讲, 看完可以参考我下面写的。
扫描线的算法如下： 图片来源：[POJ1151 Atlantis（线段树，扫描线，离散化，矩形面积并）_riba2534的博客-CSDN博客](https://riba2534.blog.csdn.net/article/details/76851233) ![[Pasted image 20220803221009.png]] ![[Pasted image 20220803221013.png]] ![[Pasted image 20220803221018.png]] 遇到新边时则扩大, 碰到之前的上边时就缩小
![[Pasted image 20220803221022.png]] ![[Pasted image 20220803221026.png]] ![[Pasted image 20220803221029.png]] ![[Pasted image 20220803221034.png]]
大概思路大佬那篇讲的很棒了, 我这里就配合代码讲一讲过程。
题目要求多个矩形合并起来的总面积, 以上思路中可以发现, 我们只需要存储矩形的上边和下边, 求和过程中利用线段树进行长度的变化, 从一条边扫描到另一条边时就乘上它们之间的宽度,便是这段小矩形的面积。
边的存储： ~~~ c ++ struct Seg { double l,r,h; // 左端点 右端点 高度 int flag; // 区分是上边还是下边 Seg(){} Seg(double a, double b, double c, int d):l(a),r(b),h(c),flag(d){} // 构造函数 bool operator < (const Seg &b) const { return h < b.h; // 根据y1 从小到大正序排序 } // 这样就从下面开始扫扫到顶端 }edge[N]; ~~~ 计算面积时就从低到高枚举边, `res += 当前的长度 * (下一条边的高度 - 当前边的高度)` **如何求当前的长度呢？** 我们需要知道当前有哪些区间是正在被使用的, 可以用一个数组当做x轴, 每次查询就遍历一次数轴来统计当前长度, 这种方法首先很慢, 其次这里的数是包含小数, 不能只用下标来保存。
小数很好处理, 我们可以将所有点的x坐标进行排序, 然后利用在排序后的位置信息来遍历整个数轴。这种操作就是离散化。
既然是区间问题我们就可以使用线段树来解决： 每个节点储存当前区间的已被使用长度(len), 当前区间是否完全被使用(cnt)
需要用到的操作是区间更新和树根查询(t[1])： 区间更新正常来说是需要lazy懒标记来优化时间, 这里我们并不需要, 因为用到一个区间时并不会去关心它的子区间, 如果一个区间被完全使用, 那么它就可以被当做一个叶子区间（最小区间）,不需要再往下划分。
所以只需要一个 pushup 操作来更新父节点: ~~~ c ++ void pushup(int l, int r, int u) { if(t[u].cnt) // 如果当前区间被完全使用 t[u].len = x[r + 1] - x[l]; // 加上当前区间的长度 右端点-左端点 else if(l == r) // 若左右端点相同则长度为0 t[u].len = 0; else // 未被完全使用的话就是子区间被使用的长度之和 t[u].len = t[u << 1].len + t[u << 1 | 1].len; } ~~~ **为什么用 x[r + 1] 而不是 x[r]?** 线段树存的并不是当前 [l,r] 的长度, 而是 [l, r + 1] 的长度, 避免出现 [3,3] 这种即是点又是线段的情况出现, 保证每个节点都存的是一条线段, 也方便判断当前区间是否为点(l == r)。
需要构建一个树嘛？不需要, 默认值就是0,我们只用实现update方法即可： ~~~ c ++ void update(int L,int R, int l, int r, int u, int val) // LR是目标区间,lr是线段树区间 { if(L <= l && R >= r) // 若当前节点在目标区间内 { t[u].cnt += val; // val为1则加上该边, 为-1则减去该边 pushup(l,r,u); // 直接更新, 可以不用这个, 只写 t[u].len = x[r + 1] - x[l] 不过效果一样 return; } int mid = l + r >> 1; if(L <= mid) update(L,R,l,mid,u << 1, val); if(R > mid) update(L,R,mid+1,r,u<< 1 | 1, val); pushup(u); } ~~~ main函数里面就看下面代码的注释吧。 这题是相当难的一道线段树, 不仅仅是用到了扫描线扩展知识, 重要的是把每个节点的值都看成线段和每个节点都有含义这两个思想, 对于深刻理解线段树很有帮助（编的） 不过写出来之后确实感觉很棒, 各位加油！
参考博客： [【hdu1542】线段树求矩形面积并 - 拦路雨偏似雪花 - 博客园 (cnblogs.com)](https://www.cnblogs.com/KonjakJuruo/p/6024266.html) [POJ1151 Atlantis（线段树，扫描线，离散化，矩形面积并）_riba2534的博客-CSDN博客](https://riba2534.blog.csdn.net/article/details/76851233) title:代码 ~~~ c ++ #include <iostream> #include <iomanip> #include <cstring> #include <algorithm> using namespace std; const int N = 220; struct Seg { double l, r, h; int flag; Seg() {} Seg(double l, double r, double h, int flag) : l(l), r(r), h(h), flag(flag) {} bool operator<(const Seg &b) const { return h < b.h; } } edge[N];
struct Node { int cnt; // 该区间是否被完全使用上 double len; } t[N << 2]; double x[N]; // 用来离散化储存坐标x
void pushup(int l, int r, int u) { if (t[u].cnt) t[u].len = x[r + 1] - x[l]; else if (l == r) // 该区间未全被使用 t[u].len = 0; else // 当前区间没占满, 为两个子节点区间长度之和 t[u].len = t[u << 1].len + t[u << 1 | 1].len; }
void update(int L, int R, int l, int r, int u, int val) { if (L <= l && R >= r) { t[u].cnt += val; pushup(l, r, u); return; } int mid = l + r >> 1; if (L <= mid) update(L, R, l, mid, u << 1, val); if (R > mid) update(L, R, mid + 1, r, u << 1 | 1, val); pushup(l, r, u); }
int main() { cin.tie(0)->sync_with_stdio(false); // 快读 cout << fixed << setprecision(2); // 保留两位小数 iomanip int n, kase = 0; while (cin >> n && n) { memset(t, 0, sizeof t); int cnt = 0; // 用于存放数据的下标 for (int i = 0; i < n; i++) { double a, b, c, d; cin >> a >> b >> c >> d; x[cnt] = a, edge[cnt++] = Seg(a, c, b, 1); // 上边 x[cnt] = c, edge[cnt++] = Seg(a, c, d, -1); // 下边 } sort(x, x + cnt); /* for (int i = 0; i < cnt; i++) cout << x[i] << " "; cout << endl; */ sort(edge, edge + cnt); int m = unique(x, x + cnt) - x; // 不重复部分的尾部 double res = 0; for (int i = 0; i < cnt; i++) { int l = lower_bound(x, x + m, edge[i].l) - x; // 二分查找 int r = lower_bound(x, x + m, edge[i].r) - x - 1; //cout << i << ": " << l << " " << r << endl; update(l, r, 0, m, 1, edge[i].flag); // 加边 或者 减边 res += t[1].len * (edge[i + 1].h - edge[i].h); // 长 * (宽) //cout << "len : " << t[1].len << endl; } cout << "Test case #" << ++kase << "\nTotal explored area: " << res << "\n\n"; } } ~~~ 二分查找前缀和
title: 题目 有n只小动物，每只都有一个独特的编号，分别从1到n。现在他们从左到右依次排在一条直线上，顺序是乱的。 现在，我们只知道每个位置前面有几个比他小的数。请你根据给出的信息计算出每个位置上的数是多少。 n<=80000。 输入第一行是一个正整数n，表示小动物的数量。 接下来有n-1个数，第i个数表示在第i+1个位置以前有多少个比第i+1个位置上的数小的数。 输出n行，每行一个整数，表示对应位置小动物的编号。 title: input 5 1 2 1 0 title: output 2 4 5 3 1 title: 思路
画个图看看： ![[Pasted image 20220804162220.png]] 整体上来看没什么思路, 我们从后往前单独看最后一个数, 比它小的在前面有4个, 又知总共有6个数, 显然这个数就应该为5。 同理到倒数第二个数时, 前面4个数中比它小的只有一个, 故肯定为2. 枚举到导数第四个数时, 当前已经确定的位置有 [? 2 ? 4 5 ?], 且前面未确定的数中比当前数小的有2个, 说明该数应该在最后一位,为6。
因此可以推断出, `a[i] + 1` 就是 a[i] 在未确定数中的位置。
朴素方法可以声明一个 `vis[]` 数组记录每个数是否确定, 然后从1到n枚举直到未确定的数数量等于 `a[i] + 1`, 此时的下标就是该位置上的数。
优化方法： 同样是`vis`数组我们求前缀和之后可以通过二分快速找到 `a[i] + 1`。 因为每次确定一个数之后, 未确定数的数量就会变化, 不能用前缀和, 这里可以用树状数组/线段树来快速处理。
总共用到的只有区间求和和单点修改。
注意二分查询时的边界条件, 如果是这样会死循环：（我也不知道为啥） ~~~ c ++ while(l < r) { int mid = l + r + 1 >> 1; if(query(1,mid,1,n) <= a[i] + 1) l = mid; else r = mid - 1; } ~~~ title:代码 ~~~ c ++ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 8e5 + 10, M = N << 2; int t[M]; int a[N], ans[N];
void build(int l, int r, int u = 1) { if (l == r) { t[u] = 1; return; } int mid = l + r >> 1; build(l, mid, u << 1), build(mid + 1, r, u << 1 | 1); t[u] = t[u << 1] + t[u << 1 | 1]; }
int query(int L, int R, int l, int r, int u = 1) { if (L <= l && R >= r) { return t[u]; } int mid = l + r >> 1; int res = 0; if (L <= mid) res += query(L, R, l, mid, u << 1); if (R > mid) res += query(L, R, mid + 1, r, u << 1 | 1); return res; }
void modify(int idx, int l, int r, int u = 1) { if (l == r) { t[u] = 0; return; } int mid = l + r >> 1; if (mid >= idx) modify(idx, l, mid, u << 1); else modify(idx, mid + 1, r, u << 1 | 1); t[u] = t[u << 1] + t[u << 1 | 1]; }
int main() { cin.tie(0)->sync_with_stdio(false); int n; cin >> n; for (int i = 2; i <= n; i++) cin >> a[i]; build(1, n); for (int i = n; i > 0; i--) { int l = 1, r = n; while (l < r) // 二分找所有前缀和位置中等于 a[i] + 1的位置 { int mid = (l + r) >> 1; if (query(1, mid, 1, n) >= a[i] + 1) r = mid; else l = mid + 1; } ans[i] = r; modify(r, 1, n); // 将该数标记为已确定 }
for (int i = 1; i <= n; i++) cout << ans[i] << "\n"; return 0; } ~~~