童心智造2022.09.01 树状数组训练专题题解

P3431

**题目大意:**给出一个大小为n*m的矩阵，矩阵中有k个点有价值，求我们从点1,1走到点n,m的最大价值(只能向上向右走)

n,m∈(1,1e9) k∈(1,1e5)

n，m的大小都是 1~1e9很大，所以我们无法暴力进行求解

但是我们发现有价值的点的数量很少，所以我们往点之间的关系进行一个思考

设w(x,y)为走到点x,y能获得的最大价值那么w(x,y) = max(w(c,d)) (c∈(1,x) d∈(1,y))

如图 从阴影部分中选取价值最高的点给点x,y，我们继续思考如果我们能够在logn的复杂度内求出阴影部分间的最大值就好了，首先我们得在x,y之前遍历阴影里面所有的点，那么我们可以想到排序，我们只需要按照横纵坐标进行从小到大排序就可以满足在x,y之前遍历阴影里面所有的点，接下来就是想如何在logn内去维护一个最大值。我们进而想到了树状数组去维护以纵坐标或者横坐标为标准的最大值。

---

P2448

题目大意:给出一个无限长的自然数 1 2 3 …1000000000…10000000000000000000000 给你一个正整数k，有次操作

每次操作可以交换自然数的位置，例如1，5那么自然数变为5 2 3 4 1…1000000000…10000000000000000000000

最后让你求出有多少对逆序对 k <= 1e5 每次输入交换的自然数 <= 1e

交换完求逆序对是一件很简单的事情但是数据特别大的时候我们一般会采用离散化处理

题目给出了无限长的自然数 并且交换的自然数也很大，但是我们无法知道交换后每个点是什么情况，所以我们只能思考交换后点与点之间有什么联系

如图我们交换后我们发现，原自然数没有交换的，它们的位置是没有改变的。

并且发现离散化后的一个情况，原自然数没有改变位置的也可以用两个离散化后的数来表示

例如图片中的2可以用 离散化后的1或者2表示，4 5 可以用离散化后的2或者3来表示

求逆序对的时候，我们对于离散化后的1求得时候我们得思考，这个1所在的下标前面还有自然数吗？如果要的话如何求逆序对

那么对于自然数2来说我们用离散化后的2来表示他是一定小于前面离散化后>=2的情况的，所以我们依照此思想先处理好1所在下标前面的自然数再处理1

因为1可能对于1下标前的自然数也会有逆序对

对于前面出现了哪些数，我们就可以用树状数组来处理了。

---

P3531

题目大意:给出两个长度相同的的只含大写字母的字符串 a, b，每次可以交换 a中相邻两个字符，求最少的交换次数，使得 a 交换后的得到的字符串与 b 相同。

a,b <= 1e6

首先对于这个题我们先考虑什么情况是最少交换次数我们再考虑如何去交换

因为字符串中只有大写字母，所以对于字符串中可能会出现重复字符的情况

例如 AABB BBAA

因为有多个A，B可以互相选择，所以这也成了我们交换的一个难点

我们可以分为以下6种情形考虑(只看A的交换):

1. ABBBABB //ABCD

   BBABBAB

2. BBABBAB //BADC
   BABBABB

3. ABBBBBA //ABDC
   BBABBAB

4. BBBAABB //BACD
   ABBBBBA

5. BBBBBAA //BDAC
   AABBBBB

6. ABABBBB//ACBD
   BBBBAAB

我们发现对于A来说永远都是第一个A对应第一个A，第二个A对应第二个A最优所以我们可以猜测如此就是最优的

随后我们把字符串a变为 1 2 3 … n 形式

字符串b根据对应的数组进行转变，众所周知逆序对的个数和最小交换次数相同

字符串a的逆序对为0 那么字符串a变为字符串b的最小交换次数就是字符串b的逆序对个数

P3605

题目大意:给你一棵树，树上每个点有个权值wi，求每个点的子树中有多少个权值比他大

首先我们按照思路思考:对于一个点的子树求有多少个权值比他大无非就是求他的逆序对，可以用树状数组维护。但是他要我们求每个点的逆序对个数，首先我们知道对于左子树右子树如果维护同一颗树状数组的话，他们会互相影响，所以我们准备开n棵树状数组，但是我们发现如果他是链式结构的话，空间复杂度为n²了所以我们换种思路思考。能否再进入右子树之前把左子树的影响消除掉。我们发现进入右子树的时候只会对大于他的权值的有关系。所以我们只要在进入右子树之前把大于他权值的先减掉，然后返回的时候再加上就好了