昆明网站建设企业,结构优化,网页制作视频的网站建设,做产品网站多少钱L - Lookup Performance
问对于一颗二叉搜索树来说#xff0c;如果我们要找一个值域区间的值有多少个#xff0c;他会向下递归查找几次#xff0c;
设#xff0c;第iii个节点所代表的最大最小值为li,ril_i, r_ili,ri#xff0c;此时我们要查询L,RL, RL,R之间的值有多…L - Lookup Performance
问对于一颗二叉搜索树来说如果我们要找一个值域区间的值有多少个他会向下递归查找几次
设第iii个节点所代表的最大最小值为li,ril_i, r_ili,ri此时我们要查询L,RL, RL,R之间的值有多少个
如果L≤li≤ri≤RL \leq l_i \leq r_i \leq RL≤li≤ri≤R那么我们不会递归下去查询意味着当访问完这个点后不会对答案产生新的贡献。如果riLorliRr_i L \ or\ l_i RriL or liR同样的访问完这个点后我们不会递归查询下去意味着当访问完这个点后不会对答案产生新的贡献。
综上我们只要找到有多少个li,ril_i, r_ili,ri满足 ① liL,ri≥Ll_i L, r_i \geq LliL,ri≥L② riR,li≤Lr_i R, l_i \leq LriR,li≤L任意一个的点有多少个然后对数量乘以二再加上一即可。
可以看作有多少条线段与L,RL, RL,R有交并且这些线段不能包含在L,RL, RL,R里。
#include bits/stdc.husing 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;vectorint 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;
}
