列表

详情

NC25215. Mistake

描述


MINIEYE's engineer M is interviewing a candidate, R, who applies the R&D post.

To better know R's data structure competence, M asks R to implement a data structure called Segment Tree.

In general, Segment Tree is a full binary tree, which means that for each node, it can either be leaf or has two child nodes; Each Segment Tree node represents a closed integer interval, if the interval length is 1, then the node is leaf; otherwise the two child nodes represent the left and right half of the interval respectively. If a non-leaf node represents the subinterval between l to r, then m = (l + r) >> 1, the left-child of the node represents the interval from l to m, and the right-child node represents the interval between m+1 to r.

However, there's an error in R's algorithm for choosing the division point m. m selected by R's Segment Tree can be wrong, but m still meets the following requirement:

l ≤ m < r, and a full binary tree can still be successfully built despite it's a wrong Segment Tree.

Below is an example of the wrong Segment Tree built by R:

 

And on R's wrong Segment Tree, it can still locate any intervals just like the correct one. The blue arrow in the picture above shows how to locate the interval from 2 to 4 on the tree.

Define the depth of the node i is：

Node depth describes the complexity of node inquiry. The deeper the node depth is, more time it will consume on inquiry. Like the general location process, if the interval represented by the current access node is included in the target interval, the child node (if any) of that node won't be accessed again. These nodes fully included in the interval are called "Locating Leaves''.

To help R know that this error will make the inquiry less efficient, M makes q inquires, each inquiry is a pair of integers l and r, then R is asked to locate the interval between l and r and calculate the total depth of all "Locating Leaves''.


输入描述

The first row is an integer n(1≤n≤105).
The root node of R's Segment Tree represents the interval between 1 and n.
The following 2n-1 row is each node's division point m, if a node doesn't have division point, then it's the tree leaf, and it will output 0. The node order here is the pre-order of the tree.
The following row includes the integer q(1≤n≤105).
Next there are q rows, each row has two integers l and r which represent an inquiry. For the definition of l and r, please check the subject.

输出描述

Print q lines.
The ith line contains the answer to the ith query.

示例1

输入: 

6
5
1
0
3
2
0
0
4
0
0
0
5
2 4
1 4
1 5
1 6
3 6

输出: 

9
12
2
1
11

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 98ms, 内存消耗: 17120K, 提交时间: 2019-04-24 19:45:45 

#include <cstdio>
#include <iostream>
#include <vector>
#define N 110000
using namespace std;
typedef long long ll;

struct seg {
	int l, r, k;
}e[2 * N];

int n, q, tot, l[N], r[N];
ll ans[N], c[N];
vector<int> p[N], g[N];

void build(int l, int r, int d) {
	e[++ tot].l = l;
	e[tot].r = r;
	int x;
	scanf("%d", &x);
	if (x == 0) {
		e[tot].k = d;
		return;
	}
	e[tot].k = - d - 2;
	build(l, x, d + 1);
	build(x + 1 , r, d + 1);
}

int lowbit(int x) {
	return x & -x;
}

void add(int x, int k) {
	while (x <= n) {
		c[x] += k;
		x += lowbit(x);
	}
}

ll sum(int x) {
	ll ret = 0;
	while (x) {
		ret += c[x];
		x -= lowbit(x);
	}
	return ret;
}


int main() {
//	freopen("1.in", "r", stdin);
	//freopen("1.out", "w", stdout);
	scanf("%d", &n);
	build(1, n, 1);
	scanf("%d", &q);
  for (int i = 1; i <= q; i ++) {
  	scanf("%d%d", &l[i], &r[i]);
  	g[r[i]].push_back(i);
  }
  for (int i = 1; i <= tot; i ++) {
  	p[e[i].r].push_back(i);
  }
  for (int i = 1; i <= n; i ++) {
  	for (auto t: p[i]) add(e[t].l, e[t].k);
  	for (auto t: g[i]) {
  		ans[t] = sum(r[t]) - sum(l[t] - 1);
  	}
  }
  for (int i = 1; i <= q; i ++) printf("%lld\n", ans[i]);
  return 0;
}

上一题

© 2024 nowcoder.com