专栏文章

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

AAC_notonlyAC
P14521题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6wgts
此快照首次捕获于
2025/12/01 21:33
3 个月前
此快照最后确认于
2025/12/01 21:33
3 个月前
查看原文

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

挑战你谷最劣解（最慢的一次 27.65s
本人用线段树维护，主观难度上位绿（下位蓝）。
简要复述下题意：给定一颗有根树，qq 次询问每次询问给定一个值 xx，从根结点出发，每经过一个点需要加上这个点给定的值（也就是题目中的“将手中的数 xx 变为 xopuaux \mathbin{\mathrm{op}_u} a_u”），到达一个点必须满足你现在的值处于给定的区间范围内，求每个询问的 xx 能到达树上的哪些点。
我们很容易想到一个暴力：对于每一次询问都遍历一遍整棵树，直接模拟即可得出可以到达哪些点。时间复杂度 O(nq)O(nq)，可以获得 15 分。
其实我们不太需要关注一些特殊性质，直接来考虑我们的暴力有什么地方有待改善。我们发现每次询问都遍历整棵树太繁琐了，而且每次询问都是独立的，各自间不会互相影响，因此可以考虑离线处理，扫一遍树就得出答案。
于是我们可以考虑怎样扫一遍树统计出所有情况。不难看出，题中改变权值的操作只有加减，因此可以考虑直接记录一个偏移量，这样我们就可以直接得出可以到达每个点的原本询问的数 xx 的区间。很明显，在这个区间的所有数都可以到达这个点，也就是区间加，可以用数据结构维护（当然其他琳琅满目的办法也行）。最后每个 xx 单点查询即可。这样就能通过此题了。
总结一下我们的思路：将所有询问离线处理，对整棵树进行遍历，遍历到一个结点便处理出在询问中可以到达这个点的区间，进行区间加。时间复杂度 O(nlog⁡n+nlog⁡q)O(n \log n+n \log q)，常数略大，但过掉这题是没问题的。
一些细节问题详见代码。
Code:
CPP
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,q,l[5000005],r[5000005],cg[5000005],b[5000005];
int tree[10000005],tag[10000005];
vector<ll> vt[1000005];
struct node
{
	ll cnt,id;
}a[5000005];
bool cmp(node u,node v)
{
	return u.cnt<v.cnt;
}
void pushdown(ll u,ll lo,ll ro)
{
	ll mid=(lo+ro)>>1;
	tree[(u<<1)]+=(mid-lo+1)*tag[u];
	tree[(u<<1)|1]+=(ro-mid)*tag[u];
	tag[(u<<1)]+=tag[u];
	tag[(u<<1)|1]+=tag[u];
	tag[u]=0;
	return ;
}
void modify(ll u,ll lo,ll ro,ll ql,ll qr)//因为每次区间加都是加1，故省略了加的数量
{
	if(ql<=lo&&ro<=qr)
	{
		tree[u]+=ro-lo+1;
		tag[u]++;
		return ;
	}
	pushdown(u,lo,ro);
	ll mid=(lo+ro)>>1;
	if(ql<=mid) modify((u<<1),lo,mid,ql,qr);
	if(qr>mid) modify((u<<1)|1,mid+1,ro,ql,qr); 
}
ll getl(ll x)//得到最小的在询问序列中大于等于这个数的位置，左端点
{
	if(x>a[q].cnt)//判越界
	{
		return q+1;
	}
	ll lo=1,ro=q;
	while(lo<ro)
	{
		ll mid=(lo+ro)>>1;
		if(a[mid].cnt>=x) ro=mid;
		else lo=mid+1;
	}
	return lo;
}
ll getr(ll x)//得到最大的在询问序列中小于等于这个数的位置，右端点
{
	if(x<a[1].cnt)//判越界
	{
		return 0;
	}
	ll lo=1,ro=q;
	while(lo<ro)
	{
		ll mid=(lo+ro+1)>>1;
		if(a[mid].cnt<=x) lo=mid;
		else ro=mid-1;
	}
	return lo;
}
void dfs(ll u,ll fa,ll lo,ll ro,ll pyl)//pyl是偏移量
{
	for(ll i=0;i<vt[u].size();i++)
	{
		ll v=vt[u][i];
		if(v==fa) continue;
		ll newl=max(lo,l[v]-pyl),newr=min(ro,r[v]-pyl);
		//一定要取max min，到达这个点前提就是要在前面所有点限定的区间内！
		//记得要减偏移量
		ll lpos=getl(newl);
		ll rpos=getr(newr);
		//获得区间加的左右端点
		if(lpos<=rpos) 
		{
			modify(1,1,q,lpos,rpos);
		}
		dfs(v,u,newl,newr,pyl+cg[v]);
	}
}
ll query(ll u,ll lo,ll ro,ll x)
{
	if(lo==ro)
	{
		return tree[u];
	}
	pushdown(u,lo,ro);
	ll mid=(lo+ro)>>1;
	if(x<=mid) return query((u<<1),lo,mid,x);
	return query((u<<1)|1,mid+1,ro,x);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(ll i=2;i<=n;i++)
	{
		ll x;
		cin>>x>>l[i]>>r[i];
		vt[x].push_back(i);
		vt[i].push_back(x);
		//建图
	}
	for(ll i=1;i<=n;i++) 
	{
		char c;
		ll x;
		cin>>c>>x;
		if(c=='+') cg[i]=x;
		else cg[i]=-x;
		//处理出操作
	}
	for(ll i=1;i<=q;i++)
	{
		cin>>a[i].cnt;
		a[i].id=i;
	}
	sort(a+1,a+q+1,cmp);//将询问离线下来排序形成单调递增的序列
	modify(1,1,q,1,q);//根结点每个数都能到，先加上
	dfs(1,0,-3e18-10,3e18+10,cg[1]);//这里最大值尽量取大点
	for(ll i=1;i<=q;i++) 
	{
		b[a[i].id]=query(1,1,q,i);
	}
	for(ll i=1;i<=q;i++) cout<<b[i]<<endl;
}
Tip: 考试的时候写了一个多小时代码，结果第三个大样例死活不出来，以为挂了结果过了，大概是因为第三个大样例是条链导致递归层数过多爆栈了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...