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

思路

首先建图，用保存每一个节点的子节点的方式存储树。

容易证明，每一个节点，有且仅有一个区间内的数可以到达，因此我们可以通过搜索先预处理出每一个节点的可达区间。

注意，用递归实现的深度优先搜索可能会爆栈，因此要用广搜或非递归实现的深搜。

接下来，暴力的方式是对于每一个查询，遍历每一个节点，判断是否在区间内，这样的时间复杂度是

O(nq)

的，过不了此题。

注意到每一个查询的结果，是看它在多少个节点的可达区间内，因此我们考虑离散化+差分。

将每一个可达区间的两端存在数组

h

内，去重排序，利用倍增(也可以用二分)来查询数在

h

内的下标，实现离散化的效果。

创建差分数组

b

，依次将每一个节点的可达区间内所有数加1。

注意，由于多个区间端点可能重合，区间中间与区间两端的数值可能不同，我们差分时将区间的左右端点坐标翻倍，这样偶数坐标就是区间端点的值，奇数坐标就是非区间端点的值。

注意，部分节点不可达，上述处理后，它们的左端点会在右端点的右侧，这些区间特判一下，不处理。

接下来把差分数组

b

转换为普通的数组

b

。

最后查询时，设查询的数为

x

, 倍增查询

x

在

h

内的最大下标

i

，使得，

h_i \le x

，判断

x

是否在

h

内。

x

在

h

内时，输出

b_{2i}

，

x

不在

h

内，说明这个数不与任何区间端点重合，输出

b_{2i+1}

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
struct edge{//边
	int v;
	long long l, r;
	edge(long long v1,long long l1,long long r1){
		this->v=v1;
		this->l=l1;
		this->r=r1;
	}
};
struct node{//节点
	long long w, al, ar;//al和ar表示可达节点的数的区间
	vector<edge> son;
}g[500005];
struct dfs_info{//非递归实现深搜
	int p;
	long long l, r, d;
	dfs_info(int p1, long long l1, long long r1, long long d1){
		this->p=p1;
		this->l=l1;
		this->r=r1;
		this->d=d1;
	}
};
stack<dfs_info> stk;
void search(int p, long long l, long long r, long long d){
	g[p].al=l-d;
	g[p].ar=r-d;
	long long w=g[p].w;
	l+=w;r+=w;
	d+=w;
	for(int i=0;i<g[p].son.size();i++){
		stk.push(dfs_info(g[p].son[i].v,max(l, g[p].son[i].l),min(r, g[p].son[i].r), d));
	}
}
void dfs(){
    while(stk.size()){
        dfs_info f=stk.top();
        stk.pop();
        search(f.p, f.l, f.r, f.d);
    }
}
long long h[1000005];//离散化数组
long long b[2000005];//差分数组
int query(long long x, int len){//离散化查询，倍增实现(也可用二分)
	int p=0, step=len;
	while(step){
		if(p+step<=len&&h[p+step]<=x){
			p+=step;
		}else step>>=1;
	}return p;
}void adda(int l, int r, long long x){//差分区间修改
	b[l]+=x;
	b[r+1]-=x;
}
int main(){
	ios::sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	for(int v=2;v<=n;v++){//建图
		long long u,l,r;
		cin >> u >> l >> r;
		g[u].son.push_back(edge(v, l, r));
	}for(int i=1;i<=n;i++){
		char op;
		long long a;
		cin >> op >> a;
		if(op=='-')a=-a;
		g[i].w=a;
	}long long base=1e18;//由于-1e18<=x<=1e18，将[-1e18,1e18]作为根节点的可达区间
	stk.push(dfs_info(1,-base, base, 0));
	dfs();
	for(int i=1;i<=n;i++){//离散化
		h[i*2-1]=g[i].al;
		h[i*2]=g[i].ar;
	}sort(h+1, h+1+2*n);
	int len=unique(h+1, h+1+2*n)-h-1;
	for(int i=1;i<=n;i++){//差分修改
		if(g[i].al<=g[i].ar)adda(query(g[i].al, len)*2, query(g[i].ar, len)*2, 1);
	}long long su=0;
	for(int i=1;i<=2*len;i++){//将差分数组转为普通数组
		su+=b[i];
		b[i]=su;
	}
	for(int t=1;t<=q;t++){
		long long x, sum=0;
		cin >> x;
		int p=query(x, len);
		if(h[p]==x)cout << b[p*2] << "\n";//查询在区间端点上
		else if(x>h[p]){
			cout << b[p*2+1] << "\n";//查询不在区间端点上
		}else{
			return 1;
		}

	}
	return 0;
}

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

文章操作

思路

代码

相关推荐

评论

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