L - Lookup Performance

問對于一顆二叉搜索樹來說，如果我們要找一個值域區間的值有多少個，他會向下遞歸查找幾次，

設，第$i$個節點所代表的最大最小值為$l_i,r_i$，此時我們要查詢$L,R$之間的值有多少個，

• 如果$L\le l_i\le r_i\le R$，那么我們不會遞歸下去查詢，意味著當訪問完這個點后不會對答案產生新的貢獻。
• 如果$r_i<Lor{l}_i>R$，同樣的，訪問完這個點后我們不會遞歸查詢下去，意味著當訪問完這個點后不會對答案產生新的貢獻。

綜上我們只要找到，有多少個$l_i,r_i$，滿足 ① $l_i<L,r_i\ge L$，② $r_i>R,l_i\le L$任意一個的點有多少個，然后對數量乘以二再加上一即可。

可以看作有多少條線段與$L,R$有交，并且，這些線段不能包含在$L,R$里。

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int head[N], to[N], nex[N], cnt = 1;int minn[N], maxn[N], a[N << 2], tot, n, m;int l[N], r[N], st[N], ed[N], cnt1, cnt2;int root[N << 2], ls[N << 6], rs[N << 6], sum[N << 6], num;vector<int> vt[N << 2];void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs(int rt, int fa) {for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa) {continue;}dfs(to[i], rt);minn[rt] = min(minn[rt], minn[to[i]]);maxn[rt] = max(maxn[rt], maxn[to[i]]);} }void update(int &rt, int pre, int l, int r,int x, int v) {rt = ++num, ls[rt] = ls[pre], rs[rt] = rs[pre], sum[rt] = sum[pre] + v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid + 1, r, x, v);} }int query(int rt1, int rt2, int l, int r, int L, int R) {if (l >= L && r <= R) {return sum[rt2] - sum[rt1];}int mid = l + r >> 1, ans = 0;if (L <= mid) {ans += query(ls[rt1], ls[rt2], l, mid, L, R);}if (R > mid) {ans += query(rs[rt1], rs[rt2], mid + 1, r, L, R);}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);for (int i = 1, ls, rs, v; i <= n; i++) {scanf("%d %d %d", &ls, &rs, &v);minn[i] = maxn[i] = v;a[++tot] = v;if (ls) {add(i, ls);}if (rs) {add(i, rs);}}scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d %d", &l[i], &r[i]);a[++tot] = l[i], a[++tot] = r[i];}sort(a + 1, a + 1 + tot);tot = unique(a + 1, a + 1 + tot) - (a + 1);for (int i = 1; i <= n; i++) {minn[i] = maxn[i] = lower_bound(a + 1, a + 1 + tot, maxn[i]) - a;}for (int i = 1; i <= m; i++) {l[i] = lower_bound(a + 1, a + 1 + tot, l[i]) - a;r[i] = lower_bound(a + 1, a + 1 + tot, r[i]) - a;}dfs(1, 0);for (int i = 1; i <= n; i++) {st[++cnt1] = minn[i], ed[++cnt2] = maxn[i];vt[minn[i]].push_back(maxn[i]);}sort(st + 1, st + 1 + cnt1), sort(ed + 1, ed + 1 + cnt2);for (int i = 1; i <= tot; i++) {root[i] = root[i - 1];for (auto it : vt[i]) {update(root[i], root[i], 1, tot, it, 1);}}for (int i = 1; i <= m; i++) {int ans = n;ans -= (lower_bound(ed + 1, ed + 1 + cnt2, l[i]) - ed) - 1;ans -= cnt1 - (upper_bound(st + 1, st + 1 + cnt1, r[i]) - st) + 1;ans -= query(root[l[i] - 1], root[r[i]], 1, tot, l[i], r[i]);printf("%d\n", 2 * ans + 1);}return 0; }

總結

以上是生活随笔為你收集整理的L - Lookup Performance（主席树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。