# 前置知识
树状数组的基本思路和简单实现，对树状数组不了解，需要先看这篇入门，本文的题目承接这篇文章。
# AcWing 241. 楼兰图腾
在完成了分配任务之后，西部 314 来到了楼兰古城的西部。
相传很久以前这片土地上 (比楼兰古城还早) 生活着两个部落，一个部落崇拜尖刀 (V)，一个部落崇拜铁锹 (∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。
西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。
西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中 y1∼yn 是 1 到 n 的一个排列。
西部 314 打算研究这幅壁画中包含着多少个图腾。
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi>yj,yj<yk，则称这三个点构成 V 图腾；
如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi<yj,yj>yk，则称这三个点构成 ∧ 图腾；
西部 314 想知道，这 n 个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。
输入格式
第一行一个数 n。第二行是 n 个数，分别代表 y1，y2,…,yn。
输出格式
两个数，中间用空格隔开，依次为 V 的个数和 ∧ 的个数。数据范围
对于所有数据，n≤200000，且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。输入样例
5 1 5 3 2 4输出样例
3 4
# 题目分析
本题属实是有点考验阅读理解的能力了，我来翻译一下。
有两种图腾，一种类似 "A"（没有横），一种类似 "V"。然后给出一些坐标，坐标的 x 轴是 1,2,3,...,n，坐标的 y 轴是 1~n 之间任意的一个数，现在我们需要找到的就是坐标系上有多少图腾。
假设以横坐标为基准：
- 组成图腾 A 的有：
[1,2,3]，[1,3,4]，[1,2,4]，[1,2,5]; - 组成图腾 V 的有：
[2,3,5]，[2,4,5]，[3,4,5]；
# 题目分析
本题的主要难点就是在阅读理解。如果能明白题意，本题的性质就不难了。
以每个点为基准点，那么基准点左边 任意比它低的点都能和基准点右边 任意比它低的点形成图腾 “A”，这个基准点总共能形成的图腾 “A” 的数量就是左边所有点 乘以 右边所有点。
同样的原理，图腾 “V” 的数量就是基准点 左 右 所有比它高的点 相乘。
那么，我们所有的点为基准点，都计算一次数量，自然就算出来了总的图腾数量。
那么，我们需要做的事情是什么？
对于每个点，快速求出它的前和后 所有 比它大 或者 比它小 的点 的数量。
并且把这个点更新到数组当中。
涉及到求区间和点更新，无疑使用，我们今天的主角树状数组可以满足复杂度需求（数据范围 ，所以 的暴力算法会超时）。
# Code
这里一定注意，每个树状数组的节点维护的是 1~n 中每个数字出现的次数。
所以，前缀和 sum[a[i]] 就是 1~a[i] 中所有数字出现的次数。
#include <cstdio> | |
#include <cstring> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
typedef long long LL; | |
const int N = 200010; | |
int n; | |
int a[N], t[N]; | |
int Greater[N], lower[N]; | |
int lowbit(int x) { | |
return -x & x; | |
} | |
void add(int x, int c) { | |
for (int i = x; i <= n; i += lowbit(i)) t[i] += c; | |
} | |
int sum(int x) { | |
int res = 0; | |
for (int i = x; i; i -= lowbit(i)) res += t[i]; | |
return res; | |
} | |
int main() { | |
scanf("%d", &n); | |
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); | |
for (int i = 1; i <= n; i ++ ) { | |
int y = a[i]; | |
// 在已加入树状数组的所有数中统计在区间 [y + 1, n] 的数字的出现次数 | |
Greater[i] = sum(n) - sum(y); | |
// 在已加入树状数组的所有数中统计在区间 [1, y - 1] 的数字的出现次数 | |
lower[i] = sum(y - 1); | |
// 把当前 y 插入到树状数组 出现了 1 次 | |
add(y, 1); | |
} | |
memset(t, 0, sizeof t); // 清空树状数组 计算另一面 | |
LL res1 = 0, res2 = 0; | |
// 从右往左倒着跑一遍 这样就计算出来另一边啦 然后相乘 | |
for (int i = n; i >= 1; i -- ) { | |
int y = a[i]; | |
res1 += (LL)lower[i] * sum(y - 1); // A 的数量 a [i] 的两侧都是比她小的 | |
res2 += (LL)Greater[i] * (sum(n) - sum(y)); // V 的数量 | |
add(y, 1); | |
} | |
printf("%lld %lld\n", res2, res1); | |
return 0; | |
} |
# AcWing 242. 一个简单的整数问题
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数 A [i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤10^5, |d|≤10000, |A[i]|≤10^9输入样例
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 Q 1 Q 2 C 1 6 3 Q 2输出样例
4 1 2 5
# 题目描述
给出一个长度为 N 的序列，有两个操作，第一个操作是给区间 [L,R] 中的数都加上 d，第二个操作是求出数列中第 x 个数的值。
# 题目分析
考虑，标准的树状数组的操作是用前缀和完成单点增删，而本题是区间的增删，那么我们就可以模仿 正常的 前缀和数组 求区间增删的方法，使用差分数组。
差分数组：前缀和数组的 逆操作。假设 a 数组 是 b 数组的 前缀和数组，那么我们就称 b 数组 是 a 数组 的差分数组。
我们知道前缀和数组是通过逐个相加得到的，那么差分数组就可以由逐个后项减前项得到。
假设原数组为 a []，则 ** 差分数组 b []** 为 b[1]=a[1]-a[0],b[2]=a[2]-a[1],...,b[n]=a[n]-a[n-1] 。
那么差分数组有什么用呢？
我们可以考虑想在原数组的区间 [L,R] 上增加 d，那么区间 [L,R] 中每个数字都得加 d，但是如果我们求出来原数组的差分数组，只需要在差分数组的 L 位置加上 d，然后在 R+1 位置减去 d 就可以了。
使用这种方式，我们就把区间增删，变成了两个单点增删。
# Code
#include <cstdio> | |
#include <cstring> | |
#include <iostream> | |
#include <algorithm> | |
using namespace std; | |
typedef long long LL; | |
const int N = 100010; | |
int n, m; | |
int a[N]; | |
LL t[N]; | |
int lowbit(int x) { | |
return -x & x; | |
} | |
void add(int x, int k) { | |
for (int i = x; i <= n; i += lowbit(i)) t[i] += k; | |
} | |
LL sum(int x) { | |
LL res = 0; | |
for (int i = x; i; i -= lowbit(i)) res += t[i]; | |
return res; | |
} | |
int main() { | |
scanf("%d%d", &n, &m); | |
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); | |
// 直接在树状数组中 存储 原数组进行差分后的结果 | |
for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]); | |
for (int i = 1; i <= m; i ++ ) { | |
char type[2]; | |
int l, r, d; | |
scanf("%s", type); | |
if (*type == 'C') { | |
cin >> l >> r >> d; | |
// 区间修改 变成 两个单点修改 | |
add(l, d), add(r + 1, -d); | |
} else { | |
cin >> l; | |
printf("%lld\n", sum(l)); | |
} | |
} | |
return 0; | |
} |
# AcWing 243. 一个简单的整数问题 2
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A [l],A [l+1],…,A [r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A [i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤10^5,
|d|≤10000,
|A[i]|≤10^9
输入样例
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例
4
55
9
15
# 题目描述
本题在上一题的基础上，有增加了亿点点难度。不但增删的时候是区间增删，连带着查询的时候也变成了区间查询。
# 题目分析
本题是上一题的延伸，所以必须先会做上一题，先理解差分数组。
本题求的是原数组的区间和，但是我们的树状数组中存储的是原数组进行差分操作之后的结果，这就导致我们没有办法直接用原数组的前缀和。
我们假设原数组是 a[] ，那么 a [x] 的前缀和就是 a1 + a2 + ... + a[x] 。
而对于我们的树状数组来说，每一个 a[i] 都需要求一次前缀和。
用代码表示就是两重循环，这样无疑是会超时的：
for (int i = 1; i <= x; i ++ ) | |
for (int j = 1; j <= i; j ++ ) |
我们把这个过程具象化的表示出来：
a1 b1
a2 b1 b2
a3 b1 b2 b3
a4 b1 b2 b3 b4
。
。
a[x] b1 b2 b3 b4 ... bx
所以，我们想求出来 a[x] 的前缀和，其实就是把整个倒三角全加起来，这样无疑是不好做的。
但是，我们可以曲线救国，使用补集的思路。
我们先把倒三角补充完整：
b1 b2 b3 b4 ... bx
a1 b1 b2 b3 b4 ... bx
a2 b1 b2 b3 b4 ... bx
a3 b1 b2 b3 b4 ... bx
a4 b1 b2 b3 b4 ... bx
。
。
a[x] b1 b2 b3 b4 ... bx
补充之后，我们发现求 a [x] 的前缀和，也就是 a1+a2+a3+a4+...+a[x] 变成了 (b1+b2+b3+b4+...+b[x])*(x+1)-(b1+2*b2+3*b3+4*b4+...+x*b[x]) 。
也就是，整体由 x+1 个 b[1]+...+b[x] 组成，而多余的部分是： 1个b1,2个b2,3个b3,4个b4 ，以此类推，一直到 x 个 b[x] ，我们把多余这部分减去，就求出了 a [x] 的前缀和。
观察这个公式，我们发现前半部分公式 b1+b2+...+b[x] ，其实就是 b [x] 的前缀和；而后半部分公式 b1+2*b2+3*b3+4*b4+...+x*b[x] ，其实就是 x*b[x] 的前缀和。
所以，我们只要维护两个树状数组，一个存储差分数组 b [x]，一个存储差分数组的 b [x] 乘以其下标 x，就可以快速算出来 a[x] 的前缀和。
# Code
（树状数组的代码比较简单，但是分析出需要使用树状数组，和树状数组究竟要存储什么东西，就有点难。）
#include <iostream> | |
#include <cstring> | |
#include <cstdio> | |
#include <algorithm> | |
using namespace std; | |
typedef long long LL; | |
const int N = 100010; | |
int a[N]; // 原数组 | |
int n, m; | |
//tb 维护查分数组的前缀和 | |
//tbi 维护 b [i] * i 的前缀和 | |
LL tb[N], tbi[N]; | |
int lowbit(int x) { | |
return -x & x; | |
} | |
// 因为有两个 树状数组 需要传一个参数 | |
// 指明 操作的是哪一个 | |
void add(LL t[], int x, LL c) { | |
for (int i = x; i <= n; i += lowbit(i)) t[i] += c; | |
} | |
// 指明 求的是哪个树状数组的 前缀和 | |
LL sum(LL t[], int x) { | |
LL res = 0; | |
for (int i = x; i; i -= lowbit(i)) res += t[i]; | |
return res; | |
} | |
// 根据公式 求原数组 x 的前缀和 | |
LL pre_sum(int x) { | |
return sum(tb, x) * (x + 1) - sum(tbi, x); | |
} | |
int main() { | |
cin >> n >> m; | |
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); | |
for (int i = 1; i <= n; i ++ ) { | |
int b = a[i] - a[i - 1]; // 查分数组的 b | |
add(tb, i, b); // 差分的树状数组 | |
add(tbi, i, (LL)b * i); //i*b [i] 的树状数组 | |
} | |
while (m -- ) { | |
char op[2]; | |
int l, r, d; | |
scanf("%s%d%d", op, &l, &r); | |
if (*op == 'Q') { | |
printf("%lld\n", pre_sum(r) - pre_sum(l - 1)); | |
} else { | |
cin >> d; // 读入修改的数 | |
// 修改 a [l] += d 在 l 的位置 加上 d | |
add(tb, l, d), add(tbi, l, l * d); | |
// a[r + 1] -= d | |
add(tb, r + 1, -d), add(tbi, r + 1, (r + 1) * -d); | |
} | |
} | |
return 0; | |
} |
# AcWing 244. 谜一样的牛
有 n 头奶牛，已知它们的身高为 1∼n 且各不相同，但不知道每头奶牛的具体身高。
现在这 n 头奶牛站成一列，已知第 i 头牛前面有 Ai 头牛比它低，求每头奶牛的身高。
输入格式
第 1 行：输入整数 n。
第 2..n 行：每行输入一个整数 Ai，第 i 行表示第 i 头牛前面有 Ai 头牛比它低。
（注意：因为第 1 头牛前面没有牛，所以并没有将它列出）输出格式
输出包含 n 行，每行输出一个整数表示牛的身高。
第 i 行输出第 i 头牛的身高。
数据范围
1≤n≤10^5输入样例
5 1 2 1 0输出样例
2 4 5 3 1
# 题目描述
有身高为 1~n 的 n 头奶牛，每头奶牛的身高各不相同。n 个奶牛排成一列，第 i 头牛的前面有 A [i] 头牛的身高比它低。求每头奶牛的身高。
本题的题意比较抽象，不太好理解，我们通过给出的示例入手。
注意一个关键信息：每头牛的参照物都是 前面的所有牛，这也就启发我们，本题需要从后往前看。
输入数据的第一个数 5，表示总共有五头牛，第一头牛前面默认没有牛。
第二个数是 1，表示第二头牛前面还有一头牛，以此类推，最后一个数是 0，表示第五头牛前面没有牛。
那么我们从后往前推，总共五头牛：
最后一个数
a[5]=0表示没有牛的身高比它低，所以它就是最低的牛，也就是第一头牛，表示为ans[5]=1；第四个数是
a[4]=1，又因为每个数只能用一次，说明剩下的牛 (2,3,4,5) 中，有一个牛比它矮，说明它是第三头牛，表示为ans[4]=3；第三个数是
a[3]=2，表示剩下的牛 (2,4,5) 中，有两个比它矮，说明它是第五头牛，表示为ans[3]=5；第二个数是
a[2]=1，表示剩下的牛 (2,4) 中有一个比它矮，所以它是ans[4]=4；最后剩下只剩下一个 2，所以
ans[5]=2；那么最后 ans 数组就是我们得出的每头牛的身高。
# 题目分析
考虑一下，我们上面都在做什么操作？
从后往前遍历每一头牛。
每头牛的位置是
h[i]+1，因为它前面有h[i]头牛；在所有剩下的身高中，找第
h[i]+1小的数，就是当前牛的身高，并且删除该数。
在剩下的数中找第 x 小的值，我们可以使用二分法。
那我们怎么知道剩下的数与 x 的关系呢？
其实，这就可以使用树状数组了。
我们初始化每个数都在树状数组里出现 1 次，删除该数，就是用它 -1 变成 0，这样使用前缀和就可以求出前 1~t 个数与 x 的关系，如果 sum[t]>=x ，那么很显然 第 x 个小的数就存在于前 t 个数中，且可能是 t。
# Code
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
const int N = 100010; | |
int n; | |
int a[N], t[N], ans[N]; | |
int lowbit(int x) { | |
return x & -x; | |
} | |
int add(int x, int c) { | |
for (int i = x; i <= n; i += lowbit(i)) t[i] += c; | |
} | |
int sum(int x) { | |
int res = 0; | |
for (int i = x; i; i -= lowbit(i)) res += t[i]; | |
return res; | |
} | |
int main() { | |
cin >> n; | |
for (int i = 2; i <= n; i ++ ) scanf("%d", &a[i]); | |
// 原数组每个数都是 1 树状数组的节点值 就是它的长度 lowbit (i) | |
for (int i = 1; i <= n; i ++ ) t[i] = lowbit(i); | |
for (int i = n; i; i -- ) { | |
// 当前数的位置 它前面有 a [i] 个数 所以它在 a [i]+1 | |
int k = a[i] + 1; | |
int l = 1, r = n; | |
// 找到 a [i]+1 的所在位置 | |
while (l < r) { | |
int mid = l + r >> 1; | |
if (sum(mid) >= k) r = mid; | |
else l = mid + 1; | |
} | |
ans[i] = r; // 牛 i 的身高就是 r | |
add(r, -1); // 牛 i 被用过了 把它去掉 | |
} | |
for (int i = 1; i <= n; i ++ ) cout << ans[i] << endl; | |
return 0; | |
} |
END
