暑假集训 Day6 总结

前言：

练习题 AK 了，虽说第五名，但题目全部一遍过。

前置知识：

我们首先要理解树状数组这个数据结构。

以上是树状数组的表示图，每一个数组 $i$ 管他前面 $2$ 的 $i\And-i$ 二进制表示数后面零的个数次方，就是 $2^{lowbit(i)-1}$ 个数。 那什么是 lowbit 呢？举几个例子。

$$lowbit(2) = 2\\ lowbit(4) = 4\\ lowbit(5) = 1$$

接下来，我们还有修改操作，下标每一次加上 $lowbit(i)$。

void add(int x, int y) {
	for (int i = x; i <= m; i += lowbit(i)) {
		tr[i] += y;
	}
}

最后，还有查询操作，我们发现，查询操作的下标改变就是修改操作的逆推。

int ask(int x) {
	int ans = 0;

	for (int i = x; i; i -= lowbit(i)) {
		ans += tr[i];
	}

	return ans;
}

以上就是树状数组的所有模板，很有用的！

A.楼兰图腾

上午没想出来，下午听了讲才想出来。

正解思路：

首先，我们先想想这题的暴力解。我们可以先创建一个标记数组，求出所有的数出现的次数。然后通过 V 和 ^ 的判断方式，for 循环每一个中间点，看看这一个点可以贡献多少个图腾，最后输出。但这种做法一定会超时，那怎样优化呢？这里提供一种叫做树状数组的好东西。树状数组就是把查询和修改的时间复杂度都变成 $O(log(n))$。所以，我们可以快速求出中间点左边和右边比它大的数以及比它小的数，从而解决这一题。

B. 一个简单的整数问题

正解思路：

这道题接近模板题，只是引入了一点差分的思想。我们每一次修改就只用 add(l,d) 同时 add(r+1,-d) 就可以了。

C.一个简单的整数问题2

这道题甚至比第四、五题还难。难在它很难想。

正解思路：

如此，我们便可以推出求大正方形的公式:

$$\left(\sum_{i=1}^nb_i\right) \times \left(n+1\right)$$

另外，还可以推出蓝色部分的计算公式：

$$a_1+a_2+a_2+a_3+a_3+a_3\dots$$

化简为:

$$\sum_{i=1}^n b_i\times i$$

那么最后的求值公式就为:

$$\left(\sum_{i=1}^nb_i\right) \times \left(n+1\right)-\sum_{i=1}^n b_i\times i$$

公式推导完后，我们就可以根据树状数组的计算方式，求出答案了。

D.Lost Cows

这题我们可以采用树状数组加二分的思路。

正解思路：

想要用树状数组做题，就要想明白，如何单点查询，区间修改。我们可以把每一个位置有没有采用过的状态存入树状数组。从最后面往前扫，每一步取剩下第 $a_i+1$ 高的身高，而这一步求的正好是一个特殊值，且有二段性，可以用二分查找。每用一个身高，就把这个身高用树状数组标记起来。

E.Buy Tickets

正解思路：

这道题目和第四题基本一样，也是用一个位置把这个位置标记起来，每一步取剩下第 $a_i+1$ 个位置。总体来说，只用改一下输入输出即可。