MnZn 86pts WA#1#2 求助
查看原帖
MnZn 86pts WA#1#2 求助
676634
Albert_Wei楼主2023/10/4 11:07
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int N = 5e5 + 5, M = 1e6 + 5, mod = 1e9 + 7;
long long pos[N], len[N];
int n, id[N], lid[N], rid[N];
vector<int> e[N << 2], e_rev[N << 2], num;
int l[N << 1], r[N << 1], lch[N << 1], rch[N << 1];
inline void Seg_pre(int x, int L, int R) {
	l[x] = L, r[x] = R;
	lch[x] = ((L + R) >> 1) << 1;
	rch[x] = lch[x] + 1;
	num.push_back(x);
	num.push_back(x + M);
	if (L == R) {
		id[L] = x;
		e[x].push_back(x + M);
		e[x + M].push_back(x);
		return ;
	}
	int mid = (L + R) >> 1;
	Seg_pre(lch[x], L, mid);
	Seg_pre(rch[x], mid + 1, R);
	e[x].push_back(lch[x]);
	e[x].push_back(rch[x]);
	e[lch[x] + M].push_back(x + M);
	e[rch[x] + M].push_back(x + M);
}

inline void Seg_con(int x, int L, int R, int u, int flag) {
	if (L <= l[x] && r[x] <= R) {
		if (flag == 0) e[x + M].push_back(id[u]);
		else e[id[u] + M].push_back(x);
		return ;
	}
	if (r[lch[x]] >= L) Seg_con(lch[x], L, R, u, flag);
	if (l[rch[x]] <= R) Seg_con(rch[x], L, R, u, flag);
}

bool SCC_vis[N << 2];
vector<int> dfs, SCC_e[N << 2];
int SCC_col[N << 2], SCC_cnt, SCC_ind[N << 2];
inline void SCC_dfs1(int x) {
	SCC_vis[x] = true;
	for (auto i : e[x])
		if (!SCC_vis[i]) SCC_dfs1(i);
	dfs.push_back(x);
}

inline void SCC_dfs2(int x, int col) {
	SCC_col[x] = col;
	SCC_vis[x] = true;
	for (auto i : e_rev[x])
		if (!SCC_vis[i]) SCC_dfs2(i, col);
}

int SCC_l[N << 2], SCC_r[N << 2];
inline void Kahn() {
	memset(SCC_l, 0x3f, sizeof(SCC_l));
	memset(SCC_r, ~0x3f, sizeof(SCC_r));
	for (int i = 1; i <= n; i++) {
		SCC_l[SCC_col[id[i]]] = min(SCC_l[SCC_col[id[i]]], lid[i]);
		SCC_r[SCC_col[id[i]]] = max(SCC_r[SCC_col[id[i]]], rid[i]);
	}
	queue<int> q;
	for (int i = 1; i <= SCC_cnt; i++)
		q.push(i);
	while (!q.empty()) {
		int f = q.front(); q.pop();
		for (auto i : SCC_e[f]) {
			SCC_l[i] = min(SCC_l[i], SCC_l[f]);
			SCC_r[i] = max(SCC_r[i], SCC_r[f]);
			if (--SCC_ind[i] == 0) q.push(i);
		}
	}
}

inline void SCC() {
	for (auto i : num)
		for (auto j : e[i])
			e_rev[j].push_back(i);
	for (auto i : num)
		if (!SCC_vis[i]) SCC_dfs1(i);
	reverse(dfs.begin(), dfs.end());
	memset(SCC_vis, 0, sizeof(SCC_vis));
	for (auto i : dfs)
		if (!SCC_vis[i]) {
			SCC_cnt++;
			SCC_dfs2(i, SCC_cnt);
		}
	for (auto i : num)
		for (auto j : e[i])
			if (SCC_col[i] != SCC_col[j]) {
				SCC_e[SCC_col[j]].push_back(SCC_col[i]);
				SCC_ind[SCC_col[i]]++;
			}
	Kahn();
}

inline void Solve() {
	for (int i = 1; i <= n; i++) {
		lid[i] = lower_bound(pos + 1, pos + n + 1, pos[i] - len[i]) - pos;
		rid[i] = upper_bound(pos + 1, pos + n + 1, pos[i] + len[i]) - pos - 1;
	}
	Seg_pre(1, 1, n);
	for (int i = 1; i <= n; i++)
		Seg_con(1, lid[i], rid[i], i, 1);
	SCC();
	long long ans = 0;
	for (long long i = 1; i <= n; i++)
		ans = (ans + i * (SCC_r[SCC_col[id[i]]] - SCC_l[SCC_col[id[i]]] + 1)) % mod;
	cout << ans << endl;
} 
	
signed main() {
    ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> pos[i] >> len[i];
	Solve();
	return 0;
} 

2023/10/4 11:07
加载中...