列表

详情

NC15416. Interval Tree

描述

Interval tree can be regarded as an extension of traditional segment tree: each vertex in interval tree still represents a interval, but the split points do not need to be the middle point.

For example, the following picture describe an interval tree on [1,6]:



Similar with segment tree, we can do some interval queries on interval tree. And we can define the time complexity of interval [l,r] as the number of vertices we need to visit when the query is about [l,r]. 

Formally, let S[l,r] be the set of vertices v on the interval tree which satisfy one of the following 2 conditions:
(1) v's interval is a subinterval of [l,r], but vv's father's interval is not. 
(2) At least one of v's decendants satisfies (1).

And then, we can define the time complexity of [l,r] as the size of S[l,r].

For example, in the picture, all the vertices in S[2,4] has been marked as blue. So the time complexity of [2,4] in this interval tree is 66. 

Now, given an interval tree on [1,n] and have q queries. Each query is a positive integer k, you need to find out the number of different intervals of which the time complexity is exactly k.

输入描述

The input will consist of multiple test cases. Each case begins with two positive integer n and q. 

The second line contains n-1 integers, the split point of each non-leaf vertex, in the pre-order traversal. If vertex [l,r]'s split point is m, it's left child should be [l,m] and it's right child should be [m+1,r]. 

Then q lines follow. The i-th line of the following n lines is the integer k denoting the i-th query.

The input guarantees that l ≤ m < r, 1 ≤ n,q ≤ 105 , and 1 ≤ k ≤ 109  and the sum of n's and q's in all test cases will not exceed 500000.

输出描述

For each query, output a single line with a single number, the answer.

示例1

输入: 

6 7
5 1 3 2 4
1
2
3
4
5
6
7

输出: 

1
2
2
3
6
4
3

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 2359ms, 内存消耗: 41216K, 提交时间: 2018-03-29 11:27:23 

#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i,a,b) for (int i=(a),_ed=(b);i<_ed;i++)
#define pi ((db)3.14159265358979323846264338327950288L)
typedef double db;
const int N = 210000;
const int FFT_MAXN = 262144;
struct cp {
	db a, b;
	cp operator+(const cp&y)const { return cp{ a + y.a,b + y.b }; }
	cp operator-(const cp&y)const { return cp{ a - y.a,b - y.b }; }
	cp operator*(const cp&y)const { return cp{ a*y.a - b * y.b,a*y.b + b * y.a }; }
	cp operator!()const { return cp{ a,-b }; };
}nw[FFT_MAXN + 1]; int bitrev[FFT_MAXN];
void dft(cp*a, int n, int flag = 1) {
	int d = 0; while ((1 << d)*n != FFT_MAXN)d++;
	rep(i, 0, n)if (i<(bitrev[i] >> d))swap(a[i], a[bitrev[i] >> d]);
	for (int l = 2; l <= n; l <<= 1) {
		int del = FFT_MAXN / l * flag;
		for (int i = 0; i<n; i += l) {
			cp *le = a + i, *ri = a + i + (l >> 1), *w = flag == 1 ? nw : nw + FFT_MAXN;
			rep(k, 0, l >> 1) {
				cp ne = *ri**w;
				*ri = *le - ne, *le = *le + ne;
				le++, ri++, w += del;
			}
		}
	}
	if (flag != 1)rep(i, 0, n)a[i].a /= n, a[i].b /= n;
}
void fft_init() {
	int L = 0; while ((1 << L) != FFT_MAXN)L++;
	bitrev[0] = 0; rep(i, 1, FFT_MAXN)bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
	cp ste = { (double)cosl(2 * pi / FFT_MAXN),(double)sinl(2 * pi / FFT_MAXN) };
	nw[0] = nw[FFT_MAXN] = { 1,0 };
	rep(i, 1, (FFT_MAXN >> 1) + 1)nw[i] = nw[i - 1] * ste;
	rep(i, (FFT_MAXN >> 1) + 1, FFT_MAXN)nw[i] = !nw[FFT_MAXN - i];
}

void convo(int*a, int n, int*b, int m, long long*c) {
	if (n <= 16 || m <= 16)
	{
		rep(i, 0, n + m + 1) c[i] = 0;
		rep(i, 0, n + 1) rep(j, 0, m + 1) c[i + j] += a[i] * b[j];
		return;
	}
	static cp f[FFT_MAXN >> 1], g[FFT_MAXN >> 1], t[FFT_MAXN >> 1];
	int N = 2; while (N <= n + m)N <<= 1;
	rep(i, 0, N)
		if (i & 1) {
			f[i >> 1].b = (i <= n) ? a[i] : 0.0;
			g[i >> 1].b = (i <= m) ? b[i] : 0.0;
		}
		else {
			f[i >> 1].a = (i <= n) ? a[i] : 0.0;
			g[i >> 1].a = (i <= m) ? b[i] : 0.0;
		}
		dft(f, N >> 1); dft(g, N >> 1);
		int del = FFT_MAXN / (N >> 1);
		cp qua = { 0,0.25 }, one = { 1,0 }, four = { 4,0 }, *w = nw;
		rep(i, 0, N >> 1) {
			int j = i ? (N >> 1) - i : 0;
			t[i] = (four * !(f[j] * g[j]) - (!f[j] - f[i])*(!g[j] - g[i])*(one + *w))*qua;
			w += del;
		}
		dft(t, N >> 1, -1);
		rep(i, 0, n + m + 1)c[i] = (long long)(((i & 1) ? t[i >> 1].a : t[i >> 1].b) + 0.5);
}
int n, q, L[N], R[N], len, D[N], father[N];
long long ans[N], C[N];
int buildtree(int l, int r, int d) {
	ans[d]++;
	if (l == r) return 0;
	int mid; scanf("%d", &mid); len++; D[len] = d;
	int now = len; L[now] = buildtree(l, mid, d + 1);
	R[now] = buildtree(mid + 1, r, d + 1);
	if (L[now]) father[L[now]] = now;
	if (R[now]) father[R[now]] = now;
	return now;
}
int pd[N], sz[N], where, now;
vector<int>go[N];
int dfs1(int k1, int k2) {
	sz[k1] = 1;
	for (int i = 0; i<go[k1].size(); i++) {
		int j = go[k1][i];
		if (pd[j] == 0 && j != k2) sz[k1] += dfs1(j, k1);
	}
	return sz[k1];
}
void dfs2(int k1, int k2) {
	int num = n - sz[k1];
	for (int i = 0; i<go[k1].size(); i++) {
		int j = go[k1][i];
		if (pd[j] == 0 && j != k2) {
			dfs2(j, k1); num = max(num, sz[j]);
		}
	}
	if (num<now) {
		now = num; where = k1;
	}
}
int wL[3][N], wR[3][N];
void dfs3(int k1, int bo, int wL, int wR, int *LL, int *RR, int &lim) {
	if (bo == 0) wL += 2, wR += 1; else wL += 1, wR += 2; lim = max(lim, max(wL, wR));
	LL[wL]++; RR[wR]++;
	if (L[k1] && pd[L[k1]] == 0) dfs3(L[k1], 0, wL, wR, LL, RR, lim);
	if (R[k1] && pd[R[k1]] == 0) dfs3(R[k1], 1, wL, wR, LL, RR, lim);
}
struct atom {
	int type, depth, len;
};
vector<atom>A;
void dfs4(int k1, int bo, int ty, int w, int D) {
	if (bo == ty) w += 2; else w++;
	A.push_back(atom{ ty,D,w });
	if (L[k1] && pd[L[k1]] == 0) dfs4(L[k1], 0, ty, w, D);
	if (R[k1] && pd[R[k1]] == 0) dfs4(R[k1], 1, ty, w, D);
}
int pretot;
void gofather(int k) {
	A.clear();
	int wL = 0, wR = 0;
	int now = father[k];
	while (now&&pd[now] == 0) {
		if (L[now] == k) {
			wL += 2; wR++; A.push_back(atom{ 1,D[now],wL - 1 });
			if (pd[R[now]] == 0 && R[now]) dfs4(R[now], 1, 1, wL - 2, D[now]);
		}
		else {
			wR += 2; wL++; A.push_back(atom{ 0,D[now],wR - 1 });
			if (pd[L[now]] == 0 && L[now]) dfs4(L[now], 0, 0, wR - 2, D[now]);
		}
		k = now; now = father[now];
	}
}
void dowith(int k1) {
	n = dfs1(k1, 0); now = n; dfs2(k1, 0); int k = where; pd[k] = 1;
	for (int i = 0; i<3; i++)
		for (int j = 0; j <= n * 2; j++) wL[i][j] = wR[i][j] = 0;
	int num0 = 0, num1 = 0;
	if (L[k] && pd[L[k]] == 0) dfs3(L[k], 0, -1, 0, wL[0], wR[0], num0);
	if (R[k] && pd[R[k]] == 0) dfs3(R[k], 1, 0, -1, wL[1], wR[1], num1);
	for (int i = 1; i <= num0; i++) ans[i + D[k] + 2] += wL[0][i];
	for (int i = 1; i <= num1; i++) ans[i + D[k] + 2] += wR[1][i];
	convo(wL[0], num0, wR[1], num1, C);
	for (int i = 0; i <= num0 + num1; i++)
		if (C[i]) ans[i + D[k] + 2] += C[i];
	if (father[k] && pd[father[k]] == 0) gofather(k); else A.clear();
	int num2 = 0, mi = 0;
	for (int i = 0; i<A.size(); i++)
		if (A[i].type == 0) mi = max(mi, A[i].depth);
	for (int i = 0; i<A.size(); i++)
		if (A[i].type == 0) {
			int num = A[i].depth + A[i].len - mi;
			num2 = max(num2, num); wL[2][num]++;
		}
	num0 = max(num0 + 1, num1 + 1);
	for (int i = 0; i <= num0; i++) wR[0][i + 1] += wR[1][i], wL[1][i + 1] += wL[0][i];
	wR[0][0]++; wL[1][0]++;
	convo(wR[0], num0, wL[2], num2, C);
	for (int i = 0; i <= num0 + num2; i++)
		if (C[i]) ans[i + mi + 2] += C[i];
	num2 = 0, mi = 0;
	for (int i = 0; i<A.size(); i++)
		if (A[i].type) mi = max(mi, A[i].depth);
	for (int i = 0; i<A.size(); i++)
		if (A[i].type) {
			int num = A[i].depth + A[i].len - mi;
			num2 = max(num2, num); wR[2][num]++;
		}
	convo(wL[1], num0, wR[2], num2, C);
	for (int i = 0; i <= num0 + num2; i++)
		if (C[i]) ans[i + mi + 2] += C[i];
	if (L[k] && pd[L[k]] == 0) dowith(L[k]);
	if (R[k] && pd[R[k]] == 0) dowith(R[k]);
	if (father[k] && pd[father[k]] == 0) dowith(father[k]);
}
int main() {
	fft_init();
	while (scanf("%d%d", &n, &q) != -1) {
		memset(L, 0x00, sizeof L); len = 0;
		memset(R, 0x00, sizeof R);
		memset(father, 0x00, sizeof father);
		memset(ans, 0x00, sizeof ans);
		memset(pd, 0x00, sizeof pd);
		buildtree(1, n, 1);
		for (int i = 1; i <= len; i++) go[i].clear();
		for (int i = 1; i <= len; i++) {
			if (L[i]) go[i].push_back(L[i]);
			if (R[i]) go[i].push_back(R[i]);
			if (father[i]) go[i].push_back(father[i]);
		}
		dowith(1);
		for (; q; q--) {
			int k1; scanf("%d", &k1);
			printf("%lld\n", (k1<0 || k1 >= N) ? 0LL : ans[k1]);
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com