76pts求助,WA #1 #2 #8
查看原帖
76pts求助,WA #1 #2 #8
732906
4BboIkm7h楼主2024/12/12 22:30
#include<bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
#define ll long long
using namespace std;
const int N = 5e5 + 10, P = 1e9 + 7, inf = 0x3f3f3f3f;
ll a[N], b[N], ans;
int n, id[N << 4], head[N << 4], tot, low[N << 4], dfn[N << 4], c, scc[N << 4], cnt, le[N << 4], ri[N << 4], Head[N << 4], Tot, size;
bool vis[N << 4];
stack<int> st;
struct edge {
	int next, to;
} e[N << 4], E[N << 4]; //原图和缩点图
struct node {
	int l, r;
} t[N << 4];
void add(int from, int to) {
	e[++tot].to = to;
	e[tot].next = head[from];
	head[from] = tot;
}
void Add(int from, int to){
	E[++Tot].to = to;
	E[Tot].next = Head[from];
	Head[from] = Tot;
}
void dfs1(int u) {
	st.push(u);
	low[u] = dfn[u] = ++c;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (!dfn[v]) {
			dfs1(v);
			low[u] = min(low[u], low[v]);
		} else if (!scc[v]) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		int v;
		do{
			v = st.top();
			st.pop();
			scc[v] = ++cnt; //cnt是scc的个数,也是缩点图的结点个数,scc[]是每个节点所在强连通分量的编号
			//更新强连通分量中的结点个数(区间长度)
			le[cnt] = min(le[cnt], t[v].l); 
			ri[cnt] = max(ri[cnt], t[v].r);
		}while(u != v);
	}
}
//更新缩点图中每个点对应的区间
void dfs2(int u) {
	vis[u] = 1;
	for (int i = Head[u]; i; i = E[i].next) {
		int v = E[i].to;
		if (!vis[v]) {
			dfs2(v);
			le[u] = min(le[u], le[v]);
			ri[u] = max(ri[u], ri[v]);
		} else {
			le[u] = min(le[u], le[v]);
			ri[u] = max(ri[u], ri[v]);
		}
	}
}
ll count(int i){
	return ri[scc[id[i]]] - le[scc[id[i]]] + 1;
}
void build(int p, int l, int r) {
	t[p] = {l, r};
	size = max(size, p); //线段树/所建图的总节点个数为size
	if (l == r) {
		id[l] = p;
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	add(p, ls);
	add(p, rs);
}
void link(int p, int u, int L, int R) {
	if (L <= t[p].l && t[p].r <= R) {
		if (u == p) return;
		add(u, p);
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (L <= mid) link(ls, u, L, R);
	if (R > mid) link(rs, u, L, R);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
	memset(le, 0x3f, sizeof(le));
	build(1, 1, n);
	//图中节点的编号和线段树中节点编号一一对应
	//i号炸弹在线段树/所建图中的编号为id[i]
	for (int i = 1; i <= n; i++) {
		if (!b[i]) continue;
		int L = lower_bound(a + 1, a + n + 1, a[i] - b[i]) - a;
		int R = upper_bound(a + 1, a + n + 1, a[i] + b[i]) - a - 1;
		link(1, id[i], L, R); //点->区间
	}
	for(int i = 1; i <= size; i++) if(!dfn[i]) dfs1(i);
	//建缩点图
	for(int u = 1; u <= size; u++){
		for(int i = head[u]; i; i = e[i].next){
			int v = e[i].to;
			if(scc[u] == scc[v]) continue;
			Add(scc[u], scc[v]);
		}
	}
	for(int i = 1; i <= cnt; i++) dfs2(i); //更新缩点图中每个节点包含的炸弹个数
	for(int i = 1; i <= n; i++) ans = (ans + i * count(i) % P) % P;
	printf("%lld", ans);
	return 0;
}
2024/12/12 22:30
加载中...