题解：P14521 【MX-S11-T2】加减乘除

容易发现对于树上的每个点，能到达它的

x

的值是一个区间，而这个区间是好求的。

假设我们已经求出了

fa_u

的区间

[L_{fa_u}],R_{fa_u}

，而从根到

u

这条路径上要加上的

a

之和为

k

，则合法的

x

需要满足：

l_u\le x+k\le r_u

以及

L_{fa_u}\le x \le R_{fa_u}

，取这两个区间的交集即可得到

u

的区间

[L_u,R_u]

。

对于询问，就是要求有多少

i

满足

L_i\le x \le R_i

，一个简单的做法是将所有的询问的

x

与所有的

L_i,R_i

放到一起离散化，那么一个数

y

的答案即为满足

L_i\le y

的

i

的数量减去满足

R_j<y

的

j

的数量，这两个值对应的是离散化后的一个前缀。

CPP

#include <bits/stdc++.h>
using namespace std;
int fa[500005];
vector<int>g[500005];
long long l[500005], r[500005];
long long L[500005], R[500005];
long long a[500005];
char op[500005];
long long b[2000005], c[2000005];
int k[2000005];
int cnt;
__int128 one = 1;

void dfs(int x, __int128 now) {
	if (L[x] > R[x])
		return;
	b[++cnt] = L[x], k[cnt] = 1;
	b[++cnt] = R[x], k[cnt] = 2;
	for (int y : g[x]) {
		long long ll = l[y], rr = r[y];
		//ll<=p+a[x]<=rr,L[x]<=p<=R[x]
		//p<=rr-a[x],p>=ll-a[x]
		__int128 pp = now;
		if (op[x] == '+')
			pp += a[x];
		else
			pp -= a[x];
		L[y] = max(one * L[x], ll - pp), R[y] = min(one * R[x], rr - pp);
		dfs(y, pp);
	}
}
long long as[1000005];
int xl[2000005], xr[2000005];
unordered_map<long long,int>da;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, q;
	cin >> n >> q;
	for (int i = 2; i <= n; i++) {
		cin >> fa[i] >> l[i] >> r[i];
		g[fa[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++)
		cin >> op[i] >> a[i];
	R[1] = 1e18;
	L[1] = -1e18;
	dfs(1, 0);
	for (int i = 1; i <= q; i++) {
		cin >> as[i];
		b[++cnt] = as[i];
	}
	for (int i = 1; i <= cnt; i++)
		c[i] = b[i];
	sort(c + 1, c + cnt + 1);
	int nn = unique(c + 1, c + cnt + 1) - (c + 1);
	for (int i = 1; i <= cnt; i++) {
		b[i] = lower_bound(c + 1, c + nn + 1, b[i]) - c;
		if (k[i] == 1)
			xl[b[i]]++;
		if (k[i] == 2)
			xr[b[i]]++;
	}
	for (int i = 1; i <= nn; i++) {
		xl[i] += xl[i - 1];
		xr[i] += xr[i - 1];
		da[c[i]] = xl[i] - xr[i - 1];
	}
	for (int i = 1; i <= q; i++)
		cout << da[as[i]] << "\n";
}

题解：P14521 【MX-S11-T2】加减乘除

文章操作

相关推荐

评论

题解：P14521 【MX-S11-T2】加减乘除