84pts,Wa T1,2求调(线段树优化建边+tarjan缩点)
查看原帖
84pts,Wa T1,2求调(线段树优化建边+tarjan缩点)
977730
CBQZZYJ楼主2024/7/19 15:43
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 500005
using namespace std;
vector<ll> G[N << 3], B[N << 3];
ll In[N << 3], Li[N << 3], Ri[N << 3], dfn[N << 3], low[N << 3], bel[N << 3], Ls[N << 3], Rs[N << 3];
ll Lin[N << 3], n, dcnt, x[N << 3], r[N << 3], dfcnt, bcnt, rt[2];
bool vis[N << 3];
struct SegmentTree
{
#define mid (L + R >> 1ll)
    ll ls[N << 3], rs[N << 3];
    inline void build(ll &id, ll L, ll R)
    {
        id = ++dcnt;
        Li[id] = L;
        Ri[id] = R;
        if (L == R)
        {
            Lin[L] = id;
            return;
        }
        build(ls[id], L, mid);
        build(rs[id], mid + 1, R);
        G[id].push_back(ls[id]);
        //        cout<<"Edge "<<id<<' '<<ls[id]<<endl;
        //        cout<<"Edge "<<id<<' '<<rs[id]<<endl;
        G[id].push_back(rs[id]);
    }
    inline void addedge(ll id, ll L, ll R, ll l, ll r, ll v)
    {
        if (R < l || r < L || l > r)
        {
            return;
        }
        if (l <= L && R <= r)
        {
            G[v].push_back(id);
            //            cout<<"Edge "<<v<<' '<<id<<endl;
            return;
        }
        addedge(ls[id], L, mid, l, r, v);
        addedge(rs[id], mid + 1, R, l, r, v);
    }
} SGTIN;
stack<ll> stk;
inline void tarjan(ll now)
{
    low[now] = dfn[now] = ++dfcnt;
    vis[now] = 1;
    stk.push(now);
    for (auto &v : G[now])
    {
        if (!dfn[v])
        {
            tarjan(v);
            low[now] = min(low[now], low[v]);
        }
        else if (vis[v])
        {
            low[now] = min(low[now], dfn[v]);
        }
    }
    if (low[now] == dfn[now])
    {
        ++bcnt;
        Ls[bcnt] = n;
        while (1)
        {
            ll p = stk.top();
            stk.pop();
            vis[p] = 0;
            bel[p] = bcnt;
            Ls[bcnt] = min(Ls[bcnt], Li[p]);
            Rs[bcnt] = max(Rs[bcnt], Ri[p]);
            if (p == now)
            {
                break;
            }
        }
    }
}
inline void rBuild()
{
    for (ll i = 1; i <= dcnt; i++)
    {
        for (auto &v : G[i])
        {
            if (bel[i] != bel[v])
            {
                B[bel[i]].push_back(bel[v]);
                In[bel[v]]++;
            }
        }
    }
}
inline void Top()
{
    queue<ll> Q;
    for (ll i = 1; i <= bcnt; i++)
    {
        if (!In[i])
        {
            Q.push(i);
        }
    }
    while (Q.size())
    {
        ll now = Q.front();
        Q.pop();
        for (auto &v : B[now])
        {
            Ls[now] = min(Ls[now], Ls[v]);
            Rs[now] = max(Rs[now], Rs[v]);
            In[v]--;
            if (!In[v])
            {
                Q.push(v);
            }
        }
    }
}
signed main()
{
    cin >> n;
    SGTIN.build(rt[1], 1, n);
    for (ll i = 1; i <= n; i++)
    {
        cin >> x[i] >> r[i];
    }
    for (ll i = 1; i <= n; i++)
    {
        ll b = upper_bound(x + 1, x + 1 + n, x[i] + r[i]) - x - 1;
        ll a = lower_bound(x + 1, x + 1 + n, x[i] - r[i]) - x;
        if (a <= b)
        {
            SGTIN.addedge(rt[1], 1, n, a, b, Lin[i]);
        }
    }
    tarjan(1), rBuild(), Top();
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        assert(Ls[bel[Lin[i]]] <= Rs[bel[Lin[i]]]);
        (ans += 1ll * i * ((1 + Rs[bel[Lin[i]]] - Ls[bel[Lin[i]]] + mod) % mod) % mod) %= mod;
    }
    cout << ans;
}
2024/7/19 15:43
加载中...