[TIOJ] 2027. 腳步鬆散

題目連結:https://tioj.infor.org/problems/2027

---

不知道多久沒來這裡了XD，來提供一下兩個這題的做法。
一個是gamegame跟我講的做法，我覺得我應該以前都沒想過，所以紀錄一下這個有趣的作法。
這裡我們將一棵二元樹的節點集合用$\mathbb{T}$表示，並且定義幾個函數
$\text{lch}:\mathbb{T}\rightarrow\mathbb{T}, \text{lch}(x)=\text{left child of }x$
$\text{rch}:\mathbb{T}\rightarrow\mathbb{T}, \text{rch}(x)=\text{right child of }x$
$\text{sz}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{sz}(x)=\text{size of }x$
$\text{w}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{w}(x)=\min(\text{sz}(\text{lch}(x)), \text{sz}(\text{rch}(x)))$
那首先有個引理：對於任意二元樹$T$都有$\displaystyle\sum_{u \in T}\text{w}(u) = \mathcal{O}(\text{sz}(T) \log \text{sz}(T))$，證明的部分就留給讀者好了(X)
白話文講一點就是如果有一個$N$個節點的二元樹，而我們對於他每個節點作的演算法都只跟那個節點小的子樹的大小有關的話，複雜度就會是$\mathcal{O}(N \log N \cdot \text{單一操作的複雜度} )$。
回到這題，可以發現如果一個區間$[L, R]$的最大值是$a_i$若且唯若$L \in [j, i]$（其中$j$是使得$j < i \land a_j > a_i$發生的最大的$j$）跟$R \in [i, j]$（其中$j$是使得$i < j \land a_j > a_i$發生的最小的$j$），而若是我們把這種性質拿去建成一棵二元樹（也就是讓可能的編號$L$都在$i$的左子樹，可能的編號$R$都在$i$的右子樹）的話我們就會拿到笛卡爾樹。
有了笛卡爾樹後，我們還需要一個支援插入、刪除、統計有多少$X$在$\oplus M$後大於$K$的資料結構（我選擇Trie），接著就可以考慮某種類似分治的作法：

1. 計算小子樹裡面符合條件的數對
2. 把小子樹的值都從Trie裡拔掉
3. 計算大子樹裡面符合條件的數對
4. 利用Trie對每個小子樹的值查詢有幾個大子樹的值會讓他們一起成為符合條件的數對
5. 將小子樹的值都插到Trie裡

詳細可以底下參考我寫的醜醜的code

#include <bits/stdc++.h>
using namespace std;
const int N = 300000 + 5;
using Data = uint32_t;
using llu = uint64_t;

class Trie{
	private:
		uint32_t LOG_N, root;
		static constexpr uint32_t MEM = 7200000;
		struct node{
			uint32_t sub[ 2 ];
			uint32_t tot;
			node() : tot( 0 ) {
				sub[ 0 ] = sub[ 1 ] = 0;
			}
		} nodes[ MEM ];
		uint32_t mem_;
		inline uint32_t new_node() {
			nodes[ mem_ ] = node();
			return mem_++;
		}
		uint32_t insert( uint32_t t, uint32_t x, uint32_t d ) {
			if ( not t ) t = new_node();
			nodes[ t ].tot++; 
			if ( not d -- ) return t;
			nodes[ t ].sub[ ( x >> d ) & 1 ] = insert( nodes[ t ].sub[ ( x >> d ) & 1 ], x, d );
			return t;
		}
		void erase( uint32_t t, uint32_t x, uint32_t d ) {
			nodes[ t ].tot--; 
			if ( not d -- ) return;
			erase( nodes[ t ].sub[ ( x >> d ) & 1 ], x, d );
		}
		uint32_t count( uint32_t t, uint32_t m, uint32_t d, uint32_t x ) {
			if ( not d -- or not t ) return nodes[ t ].tot;
			uint32_t lc = 0, rc = 1;
			if ( ( m >> d ) & 1 ) lc = 1, rc = 0;
			uint32_t s = nodes[ nodes[ t ].sub[ rc ] ].tot, nxt = lc;
			if ( ( x >> d ) & 1 ) s = 0, nxt = rc;
			return s + count( nodes[ t ].sub[ nxt ], m, d, x );
		}
	public:
		void init( uint32_t LOG_N_ ) {
			LOG_N = LOG_N_;
			mem_ = 0;
			root = new_node();
		}
		void insert( uint32_t x ) {
			root = insert( root, x, LOG_N );
		}
		void erase( uint32_t x ) {
			erase( root, x, LOG_N );
		}
		uint32_t count( uint32_t x, uint32_t m ) {
			return count( root, m, LOG_N, x );
		}
} trie;

Data sub[ N ][ 2 ];
Data a[ N ], stk[ N ], stk_;

llu solve( Data, Data, Data );

int main() {
	ios_base::sync_with_stdio( false );
	cin.tie( nullptr );

	trie.init( 24 );
	
	int n; cin >> n;
	for ( int i = 1 ; i <= n ; ++ i )
		cin >> a[ i ];
	
	for ( int i = 1 ; i <= n ; ++ i ) {
		Data la = 0;
		for ( ; stk_ and a[ stk[ stk_ - 1 ] ] < a[ i ] ; la = stk[ -- stk_ ] );
		if ( stk_ ) {
			sub[ i ][ 0 ] = sub[ stk[ stk_ - 1 ] ][ 1 ];
			sub[ stk[ stk_ - 1 ] ][ 1 ] = i;
		} else sub[ i ][ 0 ] = la;
		stk[ stk_ ++ ] = i;
	}
	
	Data dlt = 0;
	for ( int i = 1 ; i <= n ; ++ i )
		dlt += ( not a[ i ] );
	
	cout << solve( stk[ 0 ], 1, n ) - dlt << '\n';
	
	return 0;
}

llu solve( Data idx, Data L, Data R ) {
	if ( not idx ) return 0;
	llu ret = 0;
	if ( idx - L < R - idx ) {
		ret += solve( sub[ idx ][ 0 ], L, idx - 1 );
		for ( Data i = L ; i < idx ; ++ i )
			trie.erase( a[ i ] );
		ret += solve( sub[ idx ][ 1 ], idx + 1, R );

		trie.insert( a[ idx ] );
		for ( Data i = L ; i <= idx ; ++ i )
			ret += trie.count( a[ idx ], a[ i ] );
		for ( Data i = L ; i < idx ; ++ i )
			trie.insert( a[ i ] );
	} else {
		ret += solve( sub[ idx ][ 1 ], idx + 1, R );
		for ( Data i = idx + 1 ; i <= R ; ++ i )
			trie.erase( a[ i ] );
		ret += solve( sub[ idx ][ 0 ], L, idx - 1 );

		trie.insert( a[ idx ] );
		for ( Data i = idx ; i <= R ; ++ i )
			ret += trie.count( a[ idx ], a[ i ] );
		for ( Data i = idx + 1 ; i <= R ; ++ i )
			trie.insert( a[ i ] );
	}
	return ret;
}

---

不過這題也有另一個可能比較直覺的做法，但同樣不是我想到的，雖然我一開始的確是朝這個方向去想就是了。
考慮傳統的分治方法：

1. 計算左半邊的答案
2. 計算右半邊的答案
3. 統計跨過中心的做法

顯然重點會是如何統計跨過中心的做法，所以底下來講一下如何計算跨過中心的數對。
我們先考慮最大值在左半邊的情況，因此在左半邊從右至左枚舉端點，我們可以透過另一個在右半邊的指針快速知道現在目前右半邊到哪裡都還是不會超過當前左半邊端點所造成的最大值，於是我們就可以輕鬆用個Trie維護右半邊的前綴集合，每次左端點換了一個就再查一下對於這個左端點有多少個右端點在右半邊會符合條件，然後對於最大值在右半邊的情況也可以用類似的做法做完，然後就沒了！對！就沒了！，不過因為我真的很懶，就不附code了，如果真的有需要再跟我講一下，我可能會在有空的時候把他寫完吧。