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

没有乘除法？纯粹大糖题。

Solution P14521

下文记点权为到这个点的加减值，其中减法以加负数代替；准许区间为题中的

[l,r]

。

由于点权只有加减，对于从点

1

出发的值

val

，其可以通过第

i

条边的

val

一定在一个区间内。

可以这么理解：从第

i

条边向上走，准许通过的最小值和最大值都会根据点权变化。

具体来说，关系是：设

u

为深度更小的点，则

l_i\leftarrow l_i-sum_u

，其中

sum_u

为

1

到

u

的路径上的点权和。

r_i\leftarrow r_i-sum_u

，与

l_i

同理。

能到达一个点的充要条件是初始权值属于从点

1

到该点上所有准许区间之交。

但是你直接暴力做是

\operatorname{O}(nq)

的，过不了。

考虑先把从点

1

到所有点的路径上的准许区间之交求出来。然后把询问离线下来，按照

x

排个序。

那么对于点

i

，设其从点

1

到该点上所有准许区间之交为

[L,R]

，那么它只会对

x\in[L,R]

的询问产生贡献。

显然

x\in[L,R]

的询问是一段区间，这个直接差分做区间加法就好了。至于如何找到这段区间呢？使用 lower_bound 即可。

复杂度

\operatorname{O}(n \log n)

。

Code

CPP

#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
const int N=1000005;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
int n;
struct node{
	int u,v;
	i128 l,r;int nxt;
}e[N<<2];
int head[N],cnt;
ll val[N];
void add(int u,int v,ll l,ll r){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].l=l;
	e[cnt].r=r;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
ll pl[N],pr[N];
void dfs(int now,int fa,i128 sum,i128 l,i128 r){
	sum+=val[now];
	pl[now]=l;pr[now]=r;
	for(int i=head[now],v;i;i=e[i].nxt){
		v=e[i].v;
		if(v==fa)continue;
		e[i].l-=sum;e[i].r-=sum;
		dfs(v,now,sum,max(l,e[i].l),min(r,e[i].r));
	}
}
struct query{
	int id;ll x;
	friend bool operator <(query _,query __){
		return _.x<__.x;
	}
}q[N];
int Q;
ll t[N];
int cha[N],ans[N];
void print(i128 x){
//	cout<<"check:"<<(int)x<<'\n';
	if(x<0){
		cout<<"-";
		print(-x);
		return;
	}
	if(x==0)return;
	print(x/10);
	cout<<(int)(x%10);
}
signed main(){
	fastio;
	cin>>n;
	cin>>Q;
	ll l,r;
	for(int i=2,u;i<=n;i++){
		cin>>u>>l>>r;
		add(i,u,l,r);
		add(u,i,l,r);
	}
	char opt;
	for(int i=1;i<=n;i++){
		cin>>opt>>val[i];
		if(opt=='-')val[i]=-val[i];
	}
	dfs(1,0,0,-llinf,llinf);
	for(int i=1;i<=Q;i++){
		cin>>q[i].x;
		q[i].id=i;
	}
	sort(q+1,q+Q+1);
	for(int i=1;i<=Q;i++){
		t[i]=q[i].x;
	}
	for(int i=1;i<=n;i++){
		if(pl[i]>pr[i])continue;
		int l=lower_bound(t+1,t+Q+1,pl[i])-t,r=upper_bound(t+1,t+Q+1,pr[i])-t;
		cha[l]++;cha[r]--;
	}
	int sum=0;
	for(int i=1;i<=Q;i++){
		sum+=cha[i];
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=Q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

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

文章操作

Solution P14521

相关推荐

评论

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