【算法题归纳合集】高级数据结构-树状数组_int x=1,y=1; int m,n; m=n=1; switch(m) { case 0: x

一、AcWing 241. 楼兰图腾

【题目描述】
在完成了分配任务之后，西部314来到了楼兰古城的西部。
相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用V和∧的形状来代表各自部落的图腾。
西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了$n$个点，经测量发现这$n$个点的水平位置和竖直位置是两两不同的。
西部314认为这幅壁画所包含的信息与这$n$个点的相对位置有关，因此不妨设坐标分别为$(1,y_1),(2,y_2),\dots ,(n,y_n)$，其中$y_1\sim y_n$是$1$到$n$的一个排列。
西部314打算研究这幅壁画中包含着多少个图腾。
如果三个点$(i,y_i),(j,y_j),(k,y_k)$满足$1\le i<j<k\le n$且$y_i>y_j,y_j<y_k$，则称这三个点构成V图腾；
如果三个点$(i,y_i),(j,y_j),(k,y_k)$满足$1\le i<j<k\le n$且$y_i<y_j,y_j>y_k$，则称这三个点构成∧图腾；
西部314想知道，这$n$个点中两个部落图腾的数目。
因此，你需要编写一个程序来求出V的个数和∧的个数。

【输入格式】
第一行一个数$n$。
第二行是$n$个数，分别代表$y_1,y_2,\dots ,y_n$。

【输出格式】
两个数，中间用空格隔开，依次为V的个数和∧的个数。

【数据范围】
对于所有数据，$n\le 200000$，且输出答案不会超过$int64$。
$y_1\sim y_n$是$1\sim n$的一个排列。

【输入样例】

5
1 5 3 2 4
1
2

【输出样例】

3 4
1

【分析】

---

以V为例，我们需要遍历每个中间点，即对于每一个三元组$(i,j,k)$，我们遍历$j$的位置，以$j$为最低点的V的数量为$j左边高于j的点数量\times j右边高于j的点数量$，因此我们可以正序扫描一遍数组，对于每个元素$a[i]$，统计之前比$a[i]$大的元素数量即为$i$左边高于$i$的元素数量，统计完后将$a[i]$加入到树状数组中，即$add(a[i],1)$，表示值为$a[i]$的元素出现次数加一；接着逆序扫描一遍数组，对于每个元素$a[i]$，统计之前比$a[i]$大的元素数量即为$i$右边高于$i$的元素数量，统计完后也将$a[i]$加入到树状数组中。

因此本题的完整做法如下：

• 从左向右依次遍历每个数$a[i]$，使用树状数组统计在$i$位置之前所有比$a[i]$大的数的个数、以及比$a[i]$小的数的个数。
  统计完成后，将$a[i]$加入到树状数组；
• 从右向左依次遍历每个数$a[i]$，使用树状数组统计在$i$位置之后所有比$a[i]$大的数的个数、以及比$a[i]$小的数的个数。
  统计完成后，将$a[i]$加入到树状数组；
• 枚举每一个点$i$，其之前与之后比$a[i]$大的数的个数的乘积之和即为V的总数，其之前与之后比$a[i]$小的数的个数的乘积之和即为∧的总数。

---

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 200010;
int a[N], c[N];
int ge[N], le[N];//ge[i]表示第i个数左边比它大的元素数量,le[i]比它小的元素数量
int n;
LL res1, res2;//分别表示两种图腾的数量

int lowbit(int x)
{
    return x & -x;
}

int ask(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

void add(int x, int y)
{
    for (; x <= n; x += lowbit(x)) c[x] += y;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)//顺序求一遍每个元素左边比它大或小的元素数量
    {
        cin >> a[i];
        ge[i] = ask(n) - ask(a[i]);
        le[i] = ask(a[i] - 1);
        add(a[i], 1);//将a[i]加入树状数组，即数字a[i]出现1次
    }
    memset(c, 0, sizeof c);//清空树状数组
    for (int i = n; i; i--)//逆序求一遍每个元素右边比它大或小的元素数量
    {
        res1 += (LL)ge[i] * (ask(n) - ask(a[i]));
        res2 += (LL)le[i] * ask(a[i] - 1);
        add(a[i], 1);//将a[i]加入树状数组，即数字a[i]出现1次
    }
    cout << res1 << ' ' << res2 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

二、AcWing 242. 一个简单的整数问题（区间修改，单点查询）

【题目描述】
给定长度为$N$的数列$A$，然后输入$M$行操作指令。
第一类指令形如C l r d，表示把数列中第$l\sim r$个数都加$d$。
第二类指令形如Q x，表示询问数列中第$x$个数的值。
对于每个询问，输出一个整数表示答案。

【输入格式】
第一行包含两个整数$N$和$M$。
第二行包含$N$个整数$A[i]$。
接下来$M$行表示$M$条指令，每条指令的格式如题目描述所示。

【输出格式】
对于每个询问，输出一个整数表示答案。
每个答案占一行。

【数据范围】
$1\le N,M\le 10^5$
$|d|\le 10000$
$|A[i]|\le 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
1
2
3
4
5
6
7

【输出样例】

4
1
2
5
1
2
3
4

【分析】

---

树状数组能够完成单点修改、求区间和，而本题需要完成的是区间修改、求单点值。区间修改可以使用差分数组完成，若在$a[l,r]$加上$d$，则只需要在差分数组的$l$和$r+1$处进行修改即可，即$c[l]+=d,c[r+1]-=d$，求单点的值即为求差分数组在该点的前缀和。因此可以构造一个差分树状数组，使得修改及求前缀和的操作时间复杂度都为$O(logn)$。

---

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

typedef long long LL;
const int N = 100010;
int a[N];
int n, m;
LL c[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int y)
{
    for (; x <= n; x += lowbit(x)) c[x] += y;
}

LL ask(int x)
{
    LL res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(i, a[i] - a[i - 1]);//构造差分树状数组
    }
    while (m--)
    {
        string op;
        int l, r, d;
        cin >> op >> l;
        if (op == "C")
        {
            cin >> r >> d;
            add(l, d), add(r + 1, -d);//在a[l,r]加上d即为在差分数组c[l]+d,c[r+1]-d
        }
        else cout << ask(l) << endl;//求a[l]即为求差分数组c[l]的前缀和
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

三、AcWing 243. 一个简单的整数问题2（区间修改，区间查询）

【题目描述】
给定一个长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一：

• C l r d，表示把$A[l],A[l+1],\dots ,A[r]$都加上$d$。
• Q l r，表示询问数列中第$l\sim r$个数的和。

对于每个询问，输出一个整数表示答案。

【输入格式】
第一行包含两个整数$N$和$M$。
第二行包含$N$个整数$A[i]$。
接下来$M$行表示$M$条指令，每条指令的格式如题目描述所示。

【输出格式】
对于每个询问，输出一个整数表示答案。
每个答案占一行。

【数据范围】
$1\le N,M\le 10^5$
$|d|\le 10000$
$|A[i]|\le 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
1
2
3
4
5
6
7

【输出样例】

4
55
9
15
1
2
3
4

【分析】

---

假设原数组为$a$，差分数组为$b$，我们已经知道$a[l,r]+d$等价于$b[l]+=d,b[r+1]-=d$，$a[i]$等价于$b[i]$的前缀和，那么如何算出$a[i]$的前缀和呢？

假设我们需要计算$a[1]+a[2]+\cdots +a[x]$，那么就相当于计算$(b[1])+(b[1]+b[2])+\cdots +(b[1]+b[2]+\cdots +b[x])$，如下图所示：

其中蓝色标注的是我们需要计算的结果，将其补全（红色标注）后蓝色部分即为整体减去红色部分，即$(b[1]+b[2]+\cdots +b[x])\ast (x+1)-(1\ast b[1]+2\ast b[2]+\cdots +x\ast b[x])$，可以看到式子中有两部分前缀和，一部分是$b[x]$的前缀和，另一部分是$x\ast b[x]$的前缀和，因此同时维护两个差分树状数组即可。

---

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

typedef long long LL;
const int N = 100010;
int a[N];
int n, m;
LL c1[N], c2[N];//c1[i]维护差分数组b[i]的前缀和,c2[i]维护i*b[i]的前缀和

int lowbit(int x)
{
    return x & -x;
}

void add(LL c[], int x, LL y)
{
    for (; x <= n; x += lowbit(x)) c[x] += y;
}

LL ask(LL c[], int x)//求差分树状数组c[x]的前缀和
{
    LL res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

LL prefix_ask(int x)//求原数组a[x]的前缀和
{
    return ask(c1, x) * (x + 1) - ask(c2, x);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(c1, i, a[i] - a[i - 1]);
        add(c2, i, (LL)i * (a[i] - a[i - 1]));
    }
    while (m--)
    {
        string op;
        int l, r, d;
        cin >> op >> l >> r;
        if (op == "C")
        {
            cin >> d;
            add(c1, l, d), add(c1, r + 1, -d);
            add(c2, l, l * d), add(c2, r + 1, (r + 1) * -d);
        }
        else cout << prefix_ask(r) - prefix_ask(l - 1) << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

四、AcWing 244. 谜一样的牛（树状数组+二分）

【题目描述】
有$n$头奶牛，已知它们的身高为$1\sim n$且各不相同，但不知道每头奶牛的具体身高。
现在这$n$头奶牛站成一列，已知第$i$头牛前面有$A_i$头牛比它低，求每头奶牛的身高。

【输入格式】
第$1$行：输入整数$n$。
第$2\sim n$行：每行输入一个整数$A_i$，第$i$行表示第$i$头牛前面有$A_i$头牛比它低。
（注意：因为第$1$头牛前面没有牛，所以并没有将它列出）

【输出格式】
输出包含$n$行，每行输出一个整数表示牛的身高。
第$i$行输出第$i$头牛的身高。

【数据范围】
$1\le n\le 10^5$

【输入样例】

5
1
2
1
0
1
2
3
4
5

【输出样例】

2
4
5
3
1
1
2
3
4
5

【分析】

---

我们发现，如果说第$K$头牛的前面有$A_k$头牛比它矮，那么它的身高$H_k$就是数值$1\sim n$中第$A_k+1$小的没有在$H_{k+1},H_{k+2},\sim ,H_n$中出现过的数。

所以说，我们需要建立一个长度为$n$的$1$序列$b$，刚开始都是$1$，表示$n$种身高都有$1$次使用机会，然后从$n$到$1$倒序扫描每一个$A_i$，对于每个$A_i$执行查询和修改操作。

也就是说这道题目的题意就是让我们动态维护一个$01$序列，支持查询第$k$个$1$所在的位置，以及修改序列中的一个数值。第$k$个$1$所在的位置是第一个前缀和大于等于$k$的位置，因此我们可以二分查找出这个位置，时间复杂度为$O(logn)$，每次判断$mid$的前缀和$ask(mid)$是否大于等于$k$，时间复杂度也为$O(logn)$，因此总的时间复杂度为$O(nlo{g}^{2}n)$。

---

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100010;
int h[N], c[N], res[N];
int n;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int y)
{
    for (; x <= n; x += lowbit(x)) c[x] += y;
}

int ask(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) add(i, 1);//初始每种身高都有1次使用机会
    for (int i = n; i; i--)
    {
        int k = h[i] + 1;//第i头牛前面有h[i]头牛比它低,因此第i头为剩下的身高中第h[i]+1高的
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (ask(mid) >= k) r = mid;//剩余身高中前缀和第一个大于等于k的即为第k高的身高
            else l = mid + 1;
        }
        res[i] = r;
        add(r, -1);//身高用过后使用机会-1
    }
    for (int i = 1; i <= n; i++) cout << res[i] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47