【XOR-HASHING】CF1175F

XOR-HASHING

一眼典。

考虑对于每个数随一个 long long 的权值。

那么就可以有 \(prx_r \oplus prv_{l - 1} = base_{r - l + 1}\)。

这个很难直接计数，考虑增强条件。那么就是这个段一定包含 1。
那么就是很典的问题了，问多少个包含 1 的段满足上面那个柿子。
然后考虑前驱后驱间形成的段，进行枚举即可。这里用了 reverse 实现。

#include <bits/stdc++.h>
#include <ctime>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))
#define mem(x, k) memset(x, k, sizoef(k))
#define int long long

// \yhx-12243/ 鱼大保佑！！

using namespace std;

const int _ = 3e5 + 5;
int n, a[_], rd[_], prv[_], base[_], ans;

mt19937_64 rnd(time(0));
signed main () {
	ios :: sync_with_stdio(0);
	cin >> n;
	rep(i, 1, n) {
		cin >> a[i];
		rd[i] = rnd();
		base[i] = base[i - 1] ^ rd[i];

	}
	rep(i, 1, n) prv[i] = prv[i - 1] ^ rd[a[i]];
	for (int i = 1, j = 1; i <= n; i ++) {
		if (a[i] == 1) { j = 1; ans ++; }
		else {
			j = max(j, a[i]);
			if (i >= j && (prv[i] ^ prv[i - j]) == base[j])
				ans ++;
		}
	}
	reverse(a + 1, a + 1 + n);
	rep(i, 1, n) prv[i] = rd[a[i]] ^ prv[i - 1];
	for (int i = 1, j = 1; i <= n; i ++) {
		if (a[i] == 1) { j = 1; }
		else {
			j = max(j, a[i]);
			if (i >= j && (prv[i] ^ prv[i - j]) == base[j])
				ans ++;
		}
	}
	cout << ans;
	return 0;
}
/*8
  2 4 1 3 4 2 1 2*/

正儿八经做法。

考虑枚举最大值，然后直接照搬 beautiful-segment。

启发式合并，选小的那一侧，然后询问右边是否前缀有同色即可。后者是可以是可以 ST 维护前驱的，查询区间 max 即可。

时间复杂度 \(O(n \log n)\)。