线段树优化建图+缩点求助
查看原帖
线段树优化建图+缩点求助
326254
LonginusMonkey楼主2023/10/4 16:25
#include<bits/stdc++.h>
#define int long long
#define N 500100
using namespace std;
struct node{
	int leftson, rightson;
}treein[N<<3], treeout[N<<3];
int tot = 0, s , t;
int x[N], r[N];
struct node2{
	int from, to;
}edge[N<<3];
int m;
int loc2[N];
vector<int> vec[N<<3];
int add[N]; 
void buildin(int l, int r, int &index) {
	index = ++ tot;
	if(l == r) {
		add[index] = 1;
		loc2[l] = index;
		return;
	}
	int mid = l + r >> 1;
	buildin(l, mid, treein[index].leftson); buildin(mid+1, r, treein[index].rightson);
	vec[index].push_back(treein[index].leftson);
	edge[++m] = {index, treein[index].leftson};
	edge[++m] = {index, treein[index].rightson};
	vec[index].push_back(treein[index].rightson);
}
void buildout(int l, int r, int &index) {
	index = ++ tot;
	if(l == r) {
		edge[++m] = {loc2[l], index};
		vec[loc2[l]].push_back(index);
		return;
	}
	int mid = l + r >> 1;
	buildout(l, mid, treeout[index].leftson); buildout(mid+1, r, treeout[index].rightson);
	edge[++m] = {treein[index].leftson, index};
	edge[++m] = {treein[index].rightson, index};
	vec[treeout[index].leftson].push_back(index);
	vec[treeout[index].rightson].push_back(index);
}
void build_in(int l, int r, int index, int to, int left, int right) {
	if(l >= left && r <= right) {
		vec[to].push_back(index);
		return;
	}
	if(r > left || l < right) {
		return;
	}
	int mid = l + r >> 1;
	build_in(l, mid, treein[index].leftson, to, left, right);
	build_in(mid+1, r, treein[index].rightson, to, left, right); 
}
void build_out(int l, int r, int index, int to, int left, int right) {
	if(l >= left && r <= right) {
		vec[index].push_back(to);
		return;
	}
	if(r > left || l < right) {
		return;
	}
	int mid = l + r >> 1;
	build_out(l, mid, treein[index].leftson, to, left, right);
	build_out(mid+1, r, treein[index].rightson, to, left, right); 
}
int cnt = 0;
int col[N<<3];
int Ans[N<<3];
void dfs(int index) {
	col[index] = cnt;
	Ans[cnt] += add[index];
	for(int i=0; i<vec[index].size(); ++i) {
		if(col[vec[index][i]]) continue;
		dfs(vec[index][i]);
	}
}
int vis[N<<3], point[N<<3], dfn[N<<3], low[N<<3];
int ti;
int sta[N<<3], top;
int loc[N<<3];
vector<int> vec2[N<<3];
void tarjan(int index) {
	vis[index] = 1;
	dfn[index] = low[index] = ++ti;
	sta[++top] = index;
	for(int i=0; i<vec[index].size(); ++i) {
		if(!dfn[vec[index][i]]) {
			tarjan(vec[index][i]);
			low[index]=min(low[index], low[vec[index][i]]);
		}
		else if(vis[vec[index][i]]) {
			low[index]=min(low[index], low[vec[index][i]]);
		}
	}
	if(low[index]==dfn[index]){
		while(true) {
			int u = sta[top]; top--;
			loc[u] = index;
			point[index]+=add[u];
			vis[u] = 0;
			if(u==index){
				break;
			}
		}
		vis[index] = 0;
	}
}
int dp[N<<3];
void dfs2(int index) {
	if(dp[index]!=0) {
		return;
	}
	dp[index] = point[index];
	for(int i=0; i<vec2[index].size(); ++i) {
		dfs2(vec2[index][i]);
		dp[index] += dp[vec2[index][i]];
//		dp[index] = max(dp[index], dp[vec2[index][i]] + point[index]);
	}
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; for(int i=1; i<=n; ++i) {
		cin >> x[i] >> r[i];
	}
	buildin(1, n, s); buildout(1, n, t);
	for(int i=1; i<=n; ++i) {
		int l = lower_bound(x+1, x+1+n, x[i]-r[i])-x;
		int ri = upper_bound(x+1, x+1+n, x[i]+r[i])-x-1;
		++tot;
		build_in(1, n, s, tot, l, ri); build_out(1, n, t, tot, l, ri);
	}
	int ans = 0;
	for(int i=1; i<=tot; ++i) {
		if(!dfn[i]) {
			tarjan(i);
		}
	}
	for (int i=1;i<=m;i++)
	{
		int x=loc[edge[i].from],y=loc[edge[i].to];
		if (x!=y) {
			vec2[x].push_back(y);
		}
	}
	for(int i=1; i<=n; ++i) {
//		if(!vis[i]) {
			dfs2(loc[loc2[i]]);
//			cout<<point[i]<<endl;
//		}
	}
	ans = 0;
	for(int i=1; i<=n; ++i) {
		ans += i * dp[loc[loc2[i]]];
	}
	cout << ans;
	return 0;
}
2023/10/4 16:25
加载中...