专栏文章

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

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

文章操作

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

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

大概思路：

bfs 对点保存可达区间+珂朵莉树套差分维护答案

题意：

在一棵树上，一个权值从根开始向某个节点单向移动，到某个节点的位置上会加上对应点的点权，只有在一定范围内的权值可以通过对应的边，已知初始权值，求可以到达的点的个数。

解法：

考虑移动的方向，不难发现，当且仅当一个节点的父节点可以达到，且其与父节点的边可以通过时，该节点可以达到
所以我们考虑保存每个点能被哪个范围内的权值达到，此时子节点的权值范围就是父节点的权值范围与子节点到父节点的边的边上权值范围的交集，由区间知识可知，这个交集是区间或空。（对于部分写法，例如我的做法，可能需要特判空）
对于每个点上点权的改变，我们可以记录其到根节点的总改变（包括根节点），在计算边的边上权值范围时，与总改变相减（做逆处理），得到实际的边上权值范围
实现上，我们由根节点出发，使用 bfs 进行遍历（不使用 dfs 的原因：该题部分数据为长度 5×1055\times 10^5 的链，使用 dfs 可能栈空间溢出）
当节点的可达区间被计算后，较为显然的思路时直接差分维护每个值对应的个数，但本题的值域极大，无法直接差分。这里的解决思路是使用差分优化的珂朵莉树维护答案，也可以使用离散化解决。

注意点：

  1. 本题值域极大，注意 int,long long 和 __int128 的使用，做好和时间常数的平衡
  2. 区间求交集的时候注意空集判断
  3. 该题读入量较大，需要使用正确的读入方式
  4. 根节点的初值不能是 [−1×1018,1×1018][-1\times10^{18},1\times10^{18}] ，应当至少为 [−2×1018,2×1018][-2\times10^{18},2\times10^{18}] 以避免在与根节点点权运算后错误表达了根节点区间范围

参考代码：

CPP
#include<iostream>
#include<set>
#include<queue>
using namespace std;
namespace KitoTaisu{
	char *p1,*p2,buf[32770];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,32767,stdin),p1==p2)?EOF:*p1++)
	long long read(){//快速读入 
		long long x=0,f=1;
		char ch=nc();
		while(ch<48||ch>57){
			if(ch=='-')f=-1;
			ch=nc();
		}
		while(47<ch&&ch<58){
			x=x*10+(ch^48);
			ch=nc();
		}
		return x*f;
	}
}
using KitoTaisu::read;
namespace Chtholly{
	struct Chtholly{
		long long l,r;
		mutable int val;
		bool operator <(const Chtholly a)const{
			return l<a.l;
		}
	};
	#define si set<Chtholly>::iterator
	class ChthollyTree{
		private:
			set<Chtholly> tree;
			si split(long long x){
				si it=tree.lower_bound({x,0,0});
				if(it!=tree.end()&&it->l==x)return it;
				it--;
				long long l=it->l,r=it->r;
				int val=it->val;
				tree.erase(it);
				tree.insert({l,x-1,val});
				return tree.insert({x,r,val}).first;
			}
			si get(long long x){//当只需要单个区间内的val时，可以不断开该区间，来自珂朵莉绝活的珂朵莉树降常数小技巧 
				si it=tree.lower_bound({x,0,0});
				if(it!=tree.end()&&it->l==x)return it;
				it--;
				return it;
			}
		public:
			void build(long long l,long long r,int val){
				tree.insert({l,r,val});
				tree.insert({r+1,r+1,0});//防止调用 split(r+1) 时出现错误 
			}
			void assign(long long l,long long r,int val){
				si itr=split(r+1),itl=split(l);
				tree.erase(itl,itr);
				tree.insert({l,r,val});
			}
			void add(long long x,int val){
				split(x+1);
				si it=split(x);
				it->val+=val;
			}
			void presum(){
				si itl=tree.begin(),itr=tree.end();
				int sum=0;
				for(si it=itl;it!=itr;it++){
					sum+=(it->val);
					it->val=sum;
				}
			}
			int query(long long x){
				si it=get(x);//当只需要单个区间内的val时，可以不断开该区间，来自珂朵莉绝活的珂朵莉树降常数小技巧 
				return (it->val);
			}
			void print(){
				si itl=tree.begin(),itr=tree.end();
				for(si it=itl;it!=itr;it++){
					printf("Chtholly %lld %lld %d\n",it->l,it->r,it->val);
				}
				printf("\n");
			}
	};
	#undef si
}
Chtholly::ChthollyTree tr;
struct Algebra{ //区间类型，使用结构体降低实现难度 
	__int128 l,r;
	bool soro;
	Algebra operator *(Algebra a){ //区间交 
		if(soro||a.soro)return {0,0,1}; //空值特判 
		__int128 nl=max(l,a.l),nr=min(r,a.r);
		if(nr<nl)return {0,0,1};
		return {nl,nr,0};
	}
	Algebra operator -(long long x){ //区间平移，对应根据点权改变的逆操作 
		if(soro)return {0,0,1};
		__int128 nl=l-x,nr=r-x;
		return {nl,nr,soro};
	}
};
int n,q,tot,fa[500002],head[500002];
long long rd1,rd2,rd3,a[500022];
struct Nephren{
	int to,nxt;
	long long l,r;
};
Nephren son[500002];
void add(int u,int v,long long l,long long r){
	son[++tot].nxt=head[u];
	son[tot].l=l,son[tot].r=r;
	son[tot].to=v;
	head[u]=tot;
}
struct TaisuKito{
	int x;
	__int128 sum;
	Algebra cute;
};
queue<TaisuKito> qu;
void bfs(){//不使用 dfs 的原因：该题部分数据为长度 500000 的链，使用 dfs 可能栈空间溢出 
	while(!qu.empty()){
		TaisuKito ktts0715=qu.front();
		qu.pop();
		if(ktts0715.cute.soro)continue;
		if(ktts0715.cute.l<-1000000000000000000ll){
			tr.add(-1000000000000000000ll,1);
		}
		else tr.add(ktts0715.cute.l,1);
		//当答案左区间小于 -1e18 时，我们可以不考虑小于 -1e18 的部分，这样珂朵莉树的节点就可以使用 long long 而非 __int128，降低常数 
		if(ktts0715.cute.r<1000000000000000000ll){
			tr.add(ktts0715.cute.r+1,-1);
		}
		__int128 nsum=ktts0715.sum+a[ktts0715.x];
		for(int i=head[ktts0715.x];i;i=son[i].nxt){
			qu.push({son[i].to,nsum,ktts0715.cute*(Algebra){son[i].l-nsum,son[i].r-nsum,0}});
		}
	}
}
int main(){
	n=read(),q=read();
	for(int i=1;i<n;i++){
		rd1=read(),rd2=read(),rd3=read();
		add(rd1,i+1,rd2,rd3);//这里使用链式前向星维护边，也可以使用 vector ，但 vector 常数略大 
	}
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	tr.build(-1000000000000000000ll,1000000000000000000ll,0);
	qu.push({1,0,(Algebra){-3000000000000000000ll,3000000000000000000ll,0}});//开到正负 3e18 防止与根节点点权运算后出现错误 
	bfs();
	tr.presum();//对得到的差分下珂朵莉树进行前缀和 
	while(q--){
		rd1=read();
		printf("%d\n",tr.query(rd1));
	}
	return 0;
}

评论

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

正在加载评论...