TIOJ-1857

發表於 更新於 Disqus：

(以下正題開始)
剛剛那招「比利電波」是他的其中一招必殺技，能夠瞬間殲滅無數僵屍，但只能在僵屍數量夠多的時候使用。
原來這種僵屍有個習性，當他們數量夠多時會排成一種隊伍，
構造就像一棵 $H$ 層的滿支二元樹。

第一層會有一隻編號 $1$ 的僵屍，每隻編號 $x$ 的僵屍身後都站著一隻編號 $2x$ 和 $2x+1$ 的僵屍，以此類推。也就是說 $1$ ～ $H$ 層總共會有 $2^H-1$ 隻僵屍。

比利電波只要攻擊僵屍 $1$，就會從 $1$ 傳給 $2$ 和 $3$，$2$ 再傳給 $4$、$5$，$3$傳給$6$、$7$，…，直到傳完 $H$ 層。

不幸的是，有些僵屍能夠某種程度上的抵抗「比利電波」，他們不會被打死而且也不會把電波傳到身後。幸好有些特殊的僵屍和僵屍 $1$ 有聯結，就算前面站的僵屍能抵抗電波，還是會被與 $1$ 同時被電波攻擊，並繼續向後傳下去。

聽完了解說，你決定來計算這招總共能消滅多少僵屍，以作為日後對付僵屍的參考。　

$H\le 63, N\le 10^5$

讓我們整理一下題敘，你有一顆 full binary tree，一號節點已經被染紅，每一個被染紅的節點都會把兩個孩子給染紅。並且有兩種特殊節點。

  1. 無敵節點：他不會被染紅。
  2. 紅色節點：他已經被染紅了。

最後問有幾個節點被染紅了。

最直接的作法當然就是直接從根開始 dfs，遇到特殊節點就改變狀態。
在 $H$ 到很大的時候就會顯得很慢。

回想一下 dfs 的過程，我們處理特殊節點的順序其實是根據他們的深度由淺到深來整理。
所以可以直接先把所有特殊節點給按照深度排序（以這題的編號來說，直接排序就可）。
並且維護當前的答案，一開始答案是 $2^H-1$，因為所有節點都被一號染紅了。

並且假設當前的節點編號是 $x$，我們可以往上找他的祖先，看離他最近的那個特殊節點的種類是不是跟他不同。（$x$ 的祖先會是 $\lfloor\frac{x}{2}\rfloor$）

如果不同的話，那 $x$ 為根的整棵子樹的狀態（有沒有被染紅）都會改變，所以答案會增加或減少 $2^{H - dep(x)}-1$，其中 $dep(x)$ 為 $x$ 的深度（$dep(1)=0,dep(2)=dep(3)=1,dep(4)=2\cdots$），而因為這題的特性， $dep(x)=\lfloor \log(x)\rfloor$。

由於每個點最多會有 $H$ 個祖先，且在確認一個點是不是特殊點的時候我們會需要二分搜或平衡樹來在 $\mathcal{O}(\log N)$ 的時間查找。

因此整個的時間複雜度就是 $\mathcal{O}(NH\log N)$，有點緊，注意常數。

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

signed main() {
	int t;
	cin >> t;
	while(t--) {
		int h, n;
		cin >> h >> n;
		ll ans = (1LL << h) - 1;
		vector<pair<ll, int>> arr(n);
		for(auto &[a, b] : arr)
			cin >> a >> b;
		sort(arr.begin(), arr.end());

		set<ll> defense, attack;
		attack.insert(1);
		for(const auto &[a, b] : arr) {
			ll x = a;
			while(!defense.count(x) && !attack.count(x))
				x >>= 1;

			if(defense.count(x) && b) {
				ans += (1LL << (h - __lg(a))) - 1;
				attack.insert(a);
			}
			if(attack.count(x) && !b) {
				ans -= (1LL << (h - __lg(a))) - 1;
				defense.insert(a);
			}
		}
		cout << ans << '\n';
	}
}