笛卡尔树
title: 笛卡尔树
categories:
- ICPC
tags:
- null
abbrlink: 3cbbbc13
date: 2023-03-18 00:00:00
笛卡尔树
struct DKR {
int n;
vector<int> l, r;
int root;
stack<int> st;
DKR(int nn) : n(nn), l(nn + 1), r(nn + 1), root(0) {}
// 默认为小根堆，维护最小值所在区间
// dkr.built(a,less<int>());大根堆
int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) {
while (!st.empty()) st.pop(); // 清空栈
for (int i = 1; i <= n; i++) {
int last = 0;
while (!st.empty() && cmp(a[st.top()], a[i])) {
last = st.top();
st.pop();
}
if (!st.empty()) {
r[st.top()] = i;
} else {
root = i;
}
l[i] = last;
st.push(i);
}
return root;
}
};
给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。
即构建一棵二叉树，满足：
- 每个节点的编号满足二叉搜索树的性质。
- 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。
设 $l_i,r_i$ 分别表示节点 $i$ 的左右儿子的编号（若不存在则为 $0$）。
一行两个整数，分别表示 $\operatorname{xor}{i = 1}^n i \times (l_i + 1)$ 和 $\operatorname{xor}{i = 1}^n i \times (r_i + 1)$。
这是一种数据结构，可以把一堆形如 (xi,yi) 的点对放到二叉树上，使得：
- 只看 x，树的中序遍历有序，即满足二叉搜索树（Binary Search Tree, BST）性质（左小右大）
- 只看 y，这是一个二叉堆，大根/小根堆
它的性质非常优秀，可以支持一些跟最大值有关的问题，或者是插入删除之类的问题（记录插入删除时间）
建树：发现左子树的结构不会改变，维护最右链的单调栈。每次找到位置后，将原先剩余右边子树接到新点的左子树。注意维护root,，就是 a[i]一来直接变成当前最小值，反 客 为 主，此时不但要清掉链，还要把根设置成 (i,a[i]);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
DKR dkr(n);
dkr.built(a);;
ll ans1=0, ans2 = 0;
for (int i = 1; i <= n; i++) {
ans1 ^= (ll)i * (dkr.l[i] + 1);
ans2 ^= (ll)i * (dkr.r[i] + 1);
}
cout << ans1 << " " << ans2 << endl;
}
性质 / 事实
（以小根为例）
以 u 为根的子树是一段连续的区间 （由BST性质），且u 是这段区间的最小值，且不能再向两端延伸使得最小值不变（即，这一段区间是极长的）
在 u左右子树里任选两个点，两点间的区间最小值必定是$ y_{u}$
注：两个点都可以取 u 本身，此时的区间最小值仍是$ y_{u}$
a,b 间的区间最小值为:$y_{LCA(a,b)}$
若 y 是个随机排列，x是 1,2,3…n,则树高期望为 log
Treap是一颗笛卡尔树，它依靠性质4确保复杂度
——因此我们可以动态维护笛卡尔树！
[TJOI2011] 树的序
众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：
- 空树中加入一个键值 $k$，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$。
- 在非空树中插入一个键值 $k$，若 $k$ 小于其根的键值，则在其左子树中插入 $k$，否则在其右子树中插入 $k$。
我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个.
Sol:发现a[i]满足BST的key，而二叉树后来的下标一定在先来的下面符合小根堆。以(a[i],i)建笛卡尔树。
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[x] = i;
}
DKR dkr(n);
dkr.built(a);
vector<int> ans(n + 1);
int tot = 0;
auto dfs = [&](auto self, int u) -> void {
ans[++tot] = u;
if (dkr.l[u])
self(self, dkr.l[u]);
if (dkr.r[u])
self(self, dkr.r[u]);
};
dfs(dfs, dkr.root);
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
}
随机数据下1e7级别的RMQ
主要问题ST表在于空间开不下，考虑笛卡尔树建立，但是不能求lca，空间依然不够。考虑随机数据下笛卡尔树的树高不超过logn,所以考虑直接从根暴力寻找。
int a[N], l[N], r[N];
int built(int n) {
stack<int> st;
int root = 0;
for (int i = 1; i <= n; i++) {
int last = 0;
while (!st.empty() && a[st.top()] < a[i]) {
last = st.top();
st.pop();
}
if (!st.empty())
r[st.top()] = i;
else
root = i;
l[i] = last;
st.push(i);
}
return root;
} // dfs(root);
void solve() {
int n, m, s;
cin >> n >> m >> s;
srand(s);
ull ans = 0;
for (int i = 1; i <= n; i++) a[i] = read();
int root = built(n);
for (int i = 1; i <= m; i++) {
int tl, tr;
tl = read() % n + 1, tr = read() % n + 1;
int ql = min(tl, tr), qr = max(tl, tr);
// 树高期望log
int cur = root;
while (cur < ql || cur > qr) {
if (cur < ql)
cur = r[cur];
else
cur = l[cur];
}
ans += a[cur];
}
cout << ans << endl;
}
笛卡尔树实现维护单调栈基本功能：左边第一个大的数，右边第一个大的数
对于给定由 n 个元素构成的数组。一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。https://www.luogu.com.cn/problem/CF817D
Sol:求$\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r{a_i}-\min_{i=l}^r{a_i}\right)$，考虑两部分拆式子
等价于求$\begin{aligned}
\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r{a_i}-\min_{i=l}^r{a_i}\right)=\sum_{l=1}^n\sum_{r=l}^n\max_{i=l}^r{a_i}-\sum_{l=1}^n\sum_{r=l}^n\min_{i=l}^r{a_i}
\end{aligned}$
再考虑贡献法，a[i]作为最大值的极长区间是从哪到哪，则知道了a[i]在多少个区间作为最大值，就是贡献多少次。最小值同理
struct DKR {
int n;
vector<int> ls, rs;
int root;
stack<int> st;
vector<int> nxt, pre; // 极长最左边的下标，最右边的下标
DKR(int nn) {
n = nn;
ls.resize(n + 1);
rs.resize(n + 1);
root = 0;
nxt.resize(n + 1);
pre.resize(n + 1);
}
// 默认为小根堆，维护最小值所在区间
// dkr.built(a,less<int>());大根堆
int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) {
while (!st.empty()) st.pop(); // 清空栈
for (int i = 1; i <= n; i++) {
int last = 0;
while (!st.empty() && cmp(a[st.top()], a[i])) {
last = st.top();
st.pop();
}
if (!st.empty()) {
rs[st.top()] = i;
} else {
root = i;
}
ls[i] = last;
st.push(i);
}
return root;
}
void dfs(int u) {
nxt[u] = pre[u] = u;
deb(u, ls[u], rs[u]);
if (ls[u]) {
dfs(ls[u]);
nxt[u] = max(nxt[u], nxt[ls[u]]);
pre[u] = min(pre[u], pre[ls[u]]);
}
if (rs[u]) {
dfs(rs[u]);
nxt[u] = max(nxt[u], nxt[rs[u]]);
pre[u] = min(pre[u], pre[rs[u]]);
}
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
DKR dmn(n), dmx(n);
dmn.built(a);
dmx.built(a, less<int>());
dmn.dfs(dmn.root);
dmx.dfs(dmx.root);
ll mx = 0, mn = 0;
for (int i = 1; i <= n; i++) {
ll len = (ll)max(1, i - dmn.pre[i] + 1) * max(1, (dmn.nxt[i] - (i) + 1));
mn += (ll)len * a[i];
ll len1 = (ll)max(1, i - dmx.pre[i] + 1) * max(1, (dmx.nxt[i] - (i) + 1));
mx += (ll)len1 * a[i];
}
cout << mx - mn << endl;
}