MLE on #1,2空间感觉没问题啊/dk
查看原帖
MLE on #1,2空间感觉没问题啊/dk
729386
_Fancy_楼主2025/8/29 19:24
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, mod = 1e9 + 7;
int n, tn, ll[N], rr[N], lft[5 * N], rit[5 * N];
int dfn[4 * N], low[4 * N], cnt, belong[4 * N], kcnt, ins[4 * N], top, stk[4 * N], ind[4 * N], ans;
long long x[N], trr[N];
vector<int> G[4 * N];
set<int> G1[4 * N], reG[4 * N];
void add(int u, int v) {
    G[u].push_back(v);
}
void build(int u, int l, int r) {
    tn = max(tn, n + u);
    if(l == r) {
        add(u + n, l);
        return;
    }
    int mid = l + r >> 1;
    add(u + n, n + (u << 1));
    add(u + n, n + (u << 1 | 1));
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void add(int x, int u, int tl, int tr, int l, int r) {
    if(l <= tl && tr <= r) {
        add(x, u + n);
        return;
    }
    int mid = tl + tr >> 1;
    if(l <= mid) add(x, u << 1, tl, mid, l, r);
    if(r > mid) add(x, u << 1 | 1, mid + 1, tr, l, r);
}
void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    ins[u] = 1, stk[++top] = u;
    for(int v : G[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        kcnt++;
        int x = 0;
        do {
            x = stk[top--];
            ins[x] = 0;
            belong[x] = kcnt;
            if(x <= n) {
                lft[kcnt] = min(lft[kcnt], ll[x]);
                rit[kcnt] = max(rit[kcnt], rr[x]);
            }
        } while(x != u);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    memset(lft, 0x3f, sizeof lft);
    for(int i = 1; i <= n; i++) cin >> x[i] >> trr[i];
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        int l = lower_bound(x + 1, x + n + 1, x[i] - trr[i]) - x;
        int r = upper_bound(x + 1, x + n + 1, x[i] + trr[i]) - x - 1;
        add(i, 1, 1, n, l, r);
        ll[i] = l, rr[i] = r;
        // cout << l << " " << r << "\n";
    }
    for(int i = 1; i <= tn; i++) if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= tn; i++) {
        for(int v : G[i]) {
            int bi = belong[v], bv = belong[i];
            if(bi != bv) G1[bi].insert(bv), reG[bv].insert(bi), ind[bv] = reG[bv].size();
        }
    }
    queue<int> q;
    for(int i = 1; i <= kcnt; i++) if(!ind[i]) q.push(i);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v : G1[u]) {
            lft[v] = min(lft[v], lft[u]);
            rit[v] = max(rit[v], rit[u]);
            if(--ind[v] == 0) q.push(v);
        }
    }
    for(int i = 1; i <= n; i++) ans = (ans + 1ll * i * (rit[belong[i]] - lft[belong[i]] + 1) % mod) % mod;
    cout << ans;
    return 0;
}
2025/8/29 19:24
加载中...