MnZn 求条线段树优化建图板子
查看原帖
MnZn 求条线段树优化建图板子
963559
Lu_xZ楼主2024/6/16 10:27

WA 1,2.

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 1e6 + 5, M = N << 2, P = 1e9 + 7;

int n, lb[N], rb[N];
struct Bomb{
	ll p, r;
} b[N];

int binary_serch(int i, int l, int r, int type) {
	if(!type) {
		while(l < r) {
			int mid = l + r >> 1;
			if(b[i].p - b[mid].p <= b[i].r) r = mid; 
			else l = mid + 1;
		}
	}
	else {
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if(b[mid].p  - b[i].p <= b[i].r) l = mid; 
			else r = mid - 1;
		}
	}
	return l;
}

#define ls x << 1
#define rs ls | 1

int Leaf[N];
vector<int> G[M];

int t[M];

void build(int x = 1, int l = 1, int r = n) {
	if(l == r) {
		t[x] = l;
		Leaf[l] = x;
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid), build(rs, mid + 1, r);
	G[x].eb(ls);
	G[x].eb(rs); 
}

void add(int p, int L, int R, int x = 1, int l = 1, int r = n) {
	if(L <= l && r <= R) {
		G[Leaf[p]].eb(x);
		return;
	}
	int mid = l + r >> 1;
	if(mid >= L) add(p, L, R, ls, l, mid);
	if(mid < R) add(p, L, R, rs, mid + 1, r);
}

int dfn[M], low[M], ts, stk[M], ins[M], tp, id[M], L[N], R[N], tot, deg[M];
vector<int> H[M];

vector<int> scc[M];

void Tarjan(int x) {
	dfn[x] = low[x] = ++ ts;
	ins[stk[++ tp] = x] = 1;
	for(int y : G[x]) {
		if(!dfn[y]) {
			Tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if(ins[y]) {			
			low[x] = min(low[x], dfn[y]);
		}
	}
	if(low[x] == dfn[x]) {
		int y = 0;
		L[++ tot] = n + 1;
		while(y != x) {
			ins[y = stk[tp --]] = 0;
			id[y] = tot;
			if(t[y]) {
				L[tot] = min(L[tot], lb[t[y]]);
				R[tot] = max(R[tot], rb[t[y]]);
			}
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; ++ i) {
		cin >> b[i].p >> b[i].r;
	}
	for(int i = 1; i <= n; ++ i) {
		lb[i] = binary_serch(i, 1, i, 0);
		rb[i] = binary_serch(i, i, n, 1);
	}
	build();
	for(int i = 1; i <= n; ++ i) {
		add(i, lb[i], rb[i]);
	}
	Tarjan(1);
	for(int i = 1; i <= n; ++ i)
		for(int j : G[i])
			if(id[i] != id[j]) {
				H[id[j]].eb(id[i]);
				++ deg[id[i]];
			}
	queue<int> q;
	for(int i = 1; i <= tot; ++ i) {
		if(!deg[i])
			q.push(i);
		if(!L[i]) 
			L[i] = n + 1;
	}
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for(int y : H[x]) {
			L[y] = min(L[y], L[x]);
			R[y] = max(R[y], R[x]);
			if(!-- deg[y]) {
				q.push(y);
			}
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++ i) {
		int o = id[Leaf[i]];
		ans = (ans + i * ll(R[o] - L[o] + 1)) % P;
	}
	cout << ans;
	return 0;
}
2024/6/16 10:27
加载中...