241. 楼兰图腾
?输入样例：
5
1 5 3 2 4输出样例：
3 4题解：
这题其实很难想到用树状数组来解决的。树状数组和线段树的差别差不多也在这里了。
对于树状数组的题，我们很难想到用树状数组来解决，但只要我们能够想到用树状数组来做，那么就会变得非常简单，因为树状数组的代码很简洁且好写。
对于线段树的题，一般在我们读完题目之后我们便能知道这是一个考线段树的题，但是它却非常难写，难调。
好了回到本题。
要求V字形的个数和A字形的个数。
V字形：对于一个点，只要两边的点都比它大，那么就是一个合法的形状；A字形同理。下面我都只介绍V字形的，A字形同理可得。
第一种方法：暴力，遍历每个点(假设当前遍历到x点)，求出左边比它大的数的个数sum1，再求出右边比它大的数的个数sum2，sum1*sum2就是以x这个点为低点的合法的V的个数。由于本题数据过大，此方法行不通
第二种：树状数组，这很难想到这题和树状数组有什么联系。首先我们来看一下树状数组是用来干什么的（单点修改，区间查询）。因为每个点都属于 [1,n] 且只出现一次，也就是说这些点集是 1......n 的一个排列。我们从前往后遍历，遍历到第 i 个点时（值为a[i]），那么比它大的数属于区间 [a[i]+1,n]，我们只需要求出在前 i-1 个点中 [a[i]+1,n] 出现的次数sum1，再反向遍历，求出sum2，sum1*sum2即为当前点的答案。注意：在反向遍历时，我们需要清空tree[]。
我们再来看另一个操作，tree[]数组。我们都知道，在求和时，我们是对tree[]数组操作求和，当?a[i] 出现一次我们就将 tree[a[i]] 赋值为1，如：在处理第5个点时，如a[5]=8，那么我们赋值tree[8]=1，表示 8 出现一次，没有出现就是0；比如 sum(9)-sum(5)表示的就是数字 6-9中出现的数的个数
AC代码：
#include<iostream>
using namespace std;
#define ll long long
const int N = 200020;
#include<cstring>
int a[N];//原数组
int tree[N];//树状数组
int gt[N];//gt[i] 用来统计比 a[i] 大的数的个数
int lr[N];//lr[i] 用来统计比 a[i] 大的数的个数
int n;
//lowbit函数
int lowbit(int x) {
return x & (-x);
}
//求和函数，求前缀和
//这个求和函数可以细说一下，求的是tree[]的前缀和，sum(x)=tree[1]+tree[2]+......+tree[x]
//在本题，如果一个数出现了，我们将tree[x]赋值为1。比如：4出现过了，那么tree[4]赋值为1，代表出现过
//sum(9)-sum(6)表示数字7-9出现的数的次数3。
//如sum(9)-sum(6)=3 则表示 7 8 9 全出现过；sum(9)-sum(6)=2表示 7 8 9 中共有两个数出现过
int sum(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
//更新操作 给tree[posi]加上val(本题为1)值
//在本题的意思就是将tree[posi]从0变为1，表示posi这个数已经出现过了
void add(int posi, int val) {
while (posi <= n) {
tree[posi] += val;
posi += lowbit(posi);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
int x = a[i];
gt[i] = sum(n) - sum(x);//统计在这之前比a[i]大的数出现的次数
lr[i] = sum(x - 1);//统计在这之前比a[i]小的数出现的次数
add(x, 1);//更新操作，a[i]出现了，将它赋值为1
}
memset(tree, 0, sizeof tree);//注意清空数组，非常重要
ll ans1 = 0;
ll ans2 = 0;
for (int i = n; i; i--) {
//反向再求一次
int x = a[i];
ans1 += gt[i] * (ll)(sum(n) - sum(x));
ans2 += lr[i] * (ll)(sum(x - 1));
add(x, 1);
}
cout << ans1 << " " << ans2 << endl;
return 0;
}?242. 一个简单的整数问题
输入样例：
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题解：
?我们都知道树状数组支持单点修改、区间查询。但是这里要求区间修改、单点查询。
这里我们需要引入一个差分数组和前缀和的概念。前缀和大家都知道，差分数组也知道，那么我们要怎么样才能将这两个概念结合题目呢？假设差分数组为 b[]，原数组 a[]，那么
- b1=a1
- b2=a2-a1
- b3=a3-a2
- ......
- bn=an-a(n-1)
那么
- a1=b1
- a2=b1+b2
- a3=b1+b2+b3
- ......
- an=b1+b2+b3+......+bn
那么原数组的某个值 ax 就等于这个差分数组的前缀和，树状数组可以实现差分数组前缀和的求解；单点查询解决了，我们来看一下区间修改，因为我们在查询的时候使用的是差分数组的前缀和，所以我们在修改的时候也应该对差分数组进行修改，我们要让区间 a[l,r] 加上 val，我们只需要修改两个值，b[l]+val，b[r+1]-val，这里我举例说一下，假设现在有原数组 a1=1, a2=2, a3=3, a4=4,?a5=5 和差分数组 b[]
- b1=a1=1
- b2=a2-a1=1
- b3=a3-a2=1
- b4=a4-a3=1
- b5=a5-a4=1
现在让区间 a[2,4] 加上 1，我们只需要修改: b[2]+1, b[5]-1，来看一下修改后的
- b1=1—————>b1=a1=1
- b2=2—————>b2=a2-a1+1
- b3=1—————>b3=a3-a2
- b4=1—————>b4=a4-a3
- b5=0—————>b5=a5-a4-1
然后
- a1=b1=1
- a2=b1+b2=3——>a1+a2-a1+1
- a3=b1+b2+b3=4——>a1+a2-a1+a3-a2+1
- a4=b1+b2+b3+b4=5——>a1+a2-a1+a3-a2+a4-a3+1
- a5=b1+b2+b3+b4+b5=5——>a1+a2-a1+a3-a2+a4-a3+a5-a4+1-1
发现了吗？结果和我们想的一样，a[2,4] 都加上了 1，读者也可以自己想一下为什么要这么做。来看一下代码怎么实现。
AC代码：
#include<iostream>
using namespace std;
const int N = 200010;
int tree[N];//树状数组
int a[N];//原数组
int cf[N];//差分数组
int n, m;
int lowbit(int x) {
return x & (-x);
}
void add(int x, int val) {
while (x <= n) {
tree[x] += val;
x += lowbit(x);
}
}
//求和函数
int q(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <=n; i++) {
scanf_s("%d", &a[i]);
cf[i] = a[i] - a[i - 1];//差分数组
add(i, cf[i]);
}
while (m--) {
char op;
cin >> op;
if (op == 'Q') {
int l;
cin >> l;
cout << q(l) << endl;
}
else {
int l, r, d;
cin >> l >> r >> d;
add(l, d);
add(r + 1, -d);
}
}
return 0;
}243. 一个简单的整数问题2
?输入样例：
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题解：
处理完? 单点修改、区间查询，之后是? 区间修改、单点查询，现在是? 区间修改、区间查询
这里我引用一下 AcWing 大佬彩色铅笔的一张图，如有冒犯，请联系删除（本人太懒，不想画）
图中的 d[] 是差分数组，a[] 是原数组。这张图很 diao。区间修改、区间查询都解决了，来看一下代码?
AC代码：
#include<iostream>
using namespace std;
#define ll long long
const ll N = 200010;
ll a[N];//原数组
ll cf[N];//差分数组
ll tree_1[N];//差分数组的树状数组
ll tree_2[N];// i*cf[i]的树状数组
ll n, m;
ll lowbit(ll x) {
return x & -x;
}
//更新
void add(ll tree[], ll x, ll val) {
while (x <= n) {
tree[x] += val;
x += lowbit(x);
}
}
//求和
ll sum(ll tree[], ll x) {
if (x == 0) return 0;
ll ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cf[i] = a[i] - a[i - 1];
add(tree_1, i, cf[i]);
add(tree_2, i, (ll)i * cf[i]);
}
while (m--) {
char op;
cin >> op;
if (op == 'Q') {
ll l, r;
cin >> l >> r;
ll sr = sum(tree_1, r) * (r + 1) - sum(tree_2, r);
ll sl = sum(tree_1, l - 1) * (l)-sum(tree_2, l - 1);
cout << sr - sl << endl;
}
else {
ll l, r, d;
cin >> l >> r >> d;
//更新差分数组
add(tree_1, l, d);
add(tree_1, r + 1, -d);
//更新 i*cf[i] 数组
add(tree_2, l, (ll)l * d);
add(tree_2, r + 1, (ll)(r + 1) * -d);
}
}
return 0;
}244. 谜一样的牛
?输入样例：
5
1
2
1
0输出样例：
2
4
5
3
1题解：
题意是 已知一头牛前面有多少头牛比它矮，求这头牛的高度。
那不是很简单吗？假设一头牛前有3头牛比它矮，那它的身高就是 4 啊。
AC代码：
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int tree[N];
int ans[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int val) {
while (x <= n) {
tree[x] += val;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
tree[i] = lowbit(i);
}
for (int i = n; i; i--) {
int l = 1, r = n;
int mid;
while (l < r) {
mid = (l + r) >> 1;
if (sum(mid) >= a[i] + 1) r = mid;
else l = mid + 1;
}
ans[i] = r;
add(r, -1);
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
return 0;
}