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)\)。