笛卡尔树，极值分治
给定一个序列，每次以最大值将序列划分为两部分，并递归划分。这样就形成了一棵 \(n\) 个节点的二叉树，并且每个节点一定是子树中值最大的一个。
性质：区间内深度最小的点，或者两端点的 \(\operatorname{lca}\)，一定都是区间内的最大值。
我们可以使用笛卡尔树（极值分治）来统计区间极值产生的贡献。
给定长度为 \(n\) 的数组 \(a_{1\sim n}\)，问有多少对 \(l,r\) 满足 \(a_l\oplus a_r>\max_{i=l}^r\{a_i\}\)。
\(n\le 4\times 10^5,\ a_i\le 10^6\)
考虑笛卡尔树，每次找到最大值，将区间分成两部分，然后统计当前最大值的贡献。我们可以将一侧区间建出字典树，然后依次处理另一半的元素，这是容易的。
然而笛卡尔树的 \(\sum sz\) 没有保证。考虑启发式合并，保留重儿子的 Trie 树即可。
代码
| #include<iostream>
using namespace std;
const int N = 4e5 + 10;
const int V = 1.1e6;
int n;
int a[N];
int sta[N], top;
int ls[N], rs[N], rt;
int chd[2 * V][2], sz[2 * V], nn = 1;
inline int addNode() {
++nn;
chd[nn][0] = chd[nn][1] = sz[nn] = 0;
return nn;
}
inline void clear() {
nn = 1;
chd[1][0] = chd[1][1] = sz[1] = 0;
}
inline void insert(int v) {
int cur = 1;
for(int i = 19; i >= 0; i--) {
++sz[cur];
int d = (bool)(v & (1 << i));
if(!chd[cur][d]) chd[cur][d] = addNode();
cur = chd[cur][d];
}
++sz[cur];
}
inline int query(int v, int lim) {
int cur = 1, res = 0;
for(int i = 19; i >= 0; i--) {
int d1 = (bool)(v & (1 << i));
int d2 = (bool)(lim & (1 << i));
if(!d1 && !d2) {
res += sz[chd[cur][1]];
cur = chd[cur][0];
} else if(!d1 && d2) {
cur = chd[cur][1];
} else if(d1 && !d2) {
res += sz[chd[cur][0]];
cur = chd[cur][1];
} else if(d1 && d2) {
cur = chd[cur][0];
}
}
res += sz[cur];
return res;
}
long long ans;
void solve(int p, int l, int r) {
if(l == r) {
insert(a[p]);
return;
}
if(!ls[p]) {
solve(rs[p], p + 1, r);
ans += query(a[p], a[p] + 1);
insert(a[p]);
return;
}
if(!rs[p]) {
solve(ls[p], l, p - 1);
ans += query(a[p], a[p] + 1);
insert(a[p]);
return;
}
if(p <= (l + r) >> 1) {
solve(ls[p], l, p - 1);
clear();
solve(rs[p], p + 1, r);
insert(a[p]);
for(int i = l; i <= p; i++) ans += query(a[i], a[p] + 1);
for(int i = l; i < p; i++) insert(a[i]);
} else {
solve(rs[p], p + 1, r);
clear();
solve(ls[p], l, p - 1);
insert(a[p]);
for(int i = p; i <= r; i++) ans += query(a[i], a[p] + 1);
for(int i = p + 1; i <= r; i++) insert(a[i]);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
// 建立笛卡尔树：单调栈维护当前树的右链即可
rt = 1;
sta[++top] = 1;
for(int i = 2; i <= n; i++) {
int pre = 0;
while(top && a[sta[top]] < a[i]) pre = sta[top], --top;
if(sta[top]) rs[sta[top]] = i;
else rt = i;
if(pre) ls[i] = pre;
sta[++top] = i;
}
solve(rt, 1, n);
cout << ans << '\n';
return 0;
}
|
将上一题的字典树改为线段树即可。
给定一个序列，定义一段区间的最大值位置 \(\operatorname{mxp}\) 为：所有最大值中最靠左的一个。
给你一个序列 \(a_{1\sim n}\)，称一个序列 \(b_{1\sim n}\) 是合法的，当且仅当：
- \(\forall i\in [1,n],~1\le b_i\le m\)；
- \(\forall 1\le l\le r\le n,~\operatorname{mxp}_{a}[l,r]=\operatorname{mxp}_{b}[l,r]\)；
给定 \(n,m\)，请你输出合法的 \(b\) 序列的数量对 \(10^9+7\) 取模的结果。
\(nm\le 10^6\)
考虑极值分治，每次找到 \(a\) 中当前区间的 \(\operatorname{mxp}\)，将序列分成两半，然后枚举 \(b\) 在该位置的值 \(x\)，并钦定左右两侧的最大值都小于（在左边）或小于等于（在右边）\(x\) 即可。考虑 dp，设 \(f_{i,j}\) 表示在 \(i\) 管辖的区间内都合法，其中 \(b_i=j\) 时的方案数。用一个前缀和优化容易做到 \(O(nm)\)。
代码
| #include<iostream>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
const int NM = 1e6 + 10;
const int MOD = 1e9 + 7;
inline void add(int &a, int b) { a = (a + b) % MOD; }
int T;
int n, m;
int a[N];
int lc[N], rc[N], rt;
int sta[N], top;
int f[NM];
int g(int u, int i) { return (u - 1) * m + i; }
void dfs(int u) {
if(lc[u]) dfs(lc[u]);
if(rc[u]) dfs(rc[u]);
int s1 = !lc[u], s2 = !rc[u];
for(int i = 1; i <= m; i++) {
if(rc[u]) add(s2, f[g(rc[u], i)]);
f[g(u, i)] = (ll)s1 * s2 % MOD;
if(lc[u]) add(s1, f[g(lc[u], i)]);
}
}
int main() {
cin >> T;
while(T--) {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
top = 0;
sta[++top] = rt = 1;
for(int i = 1; i <= n; i++) lc[i] = rc[i] = 0;
for(int i = 2; i <= n; i++) {
int pre = 0;
while(top && a[sta[top]] < a[i]) { pre = sta[top--]; }
if(pre) lc[i] = pre;
if(top) rc[sta[top]] = i;
else rt = i;
sta[++top] = i;
}
dfs(rt);
int ans = 0;
for(int i = 1; i <= m; i++) add(ans, f[g(rt, i)]);
cout << ans << '\n';
}
return 0;
}
|