这个东西其实我是不太会的……但是勉强卡过去了。
首先肯定是建有向图，然后求每个节点能访问的节点个数，最裸的打法就是按照题意枚举建边然后tarjan缩点，用bitset记录一下访问节点，但是bitset开不了那么大，只能拿到50%的分，至于开数组枚举我没有试，目测高不了多少。
然后思考这样一个问题，我建的那么多边真的有用么。于是只建离他最近的两个点的边，然后直接topsort统计ans，能拿到80%的数据。
然后就不会了……
去loj看一眼，有一组小的hack数据，异常难受。
看看别人的打法，不是直接统计ans，而是记录这个点所能到达的最左点l[x]和最右点r[x]，然后r[x]-l[x]+1就是他能引爆的炸弹数。可以AC。
#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <stack> #include <bitset> #include <map> #define ll long long using namespace std; struct EDGE { int ed, nex; } edge[1000500], edgec[1000500]; int first[500500], firstc[500500], numc, num; struct Point { ll x, r; } p[500500]; ll read() { ll sum = 0; int f = 1; char x = getchar(); while (x < '0' || x > '9') { if (x == '-') f = -1; x = getchar(); } while (x >= '0' && x <= '9') { sum = sum * 10 + x - '0'; x = getchar(); } return sum * f; } ll n, ans1; const int mod = 1e9 + 7; const int inf=0x7fffffff; int dfn[500500], low[500500], sta[50005000], bl[500500], du[500500]; int ord, sccnum, top,l[500500],r[500500]; vector<int> scc[500500]; bool ins[500500]; void add(int st, int ed) { // cout<<"st="<<st<<" ed="<<ed<<endl; edge[++num].ed = ed; edge[num].nex = first[st]; first[st] = num; } void addc(int st, int ed) { // cout<<"stc="<<st<<" edc="<<ed<<endl; edgec[++numc].ed = ed; edgec[numc].nex = firstc[st]; firstc[st] = numc; } void topsort() { queue<int> q; for (int i = 1; i <= sccnum; i++) if (!du[i]) q.push(i); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = firstc[x]; i; i = edgec[i].nex) { int y = edgec[i].ed; du[y]--; l[y]=min(l[y],l[x]); r[y]=max(r[y],r[x]); if (!du[y]) q.push(y); } } } void tarjan(int x) { dfn[x] = low[x] = ++ord; sta[++top] = x; ins[x] = 1; for (int i = first[x]; i; i = edge[i].nex) { int y = edge[i].ed; if (!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if (ins[y]) low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x]) { sccnum++; int p; do { p = sta[top--]; ins[p] = 0; l[sccnum]=min(l[sccnum],p); r[sccnum]=max(r[sccnum],p); bl[p] = sccnum; scc[sccnum].push_back(p); } while (x != p); } } int main() { n = read(); for (int i = 1; i <= n; i++) { p[i].x = read(); p[i].r = read(); } for(int i=1;i<=n;i++){ l[i]=inf; r[i]=-inf; } for (int i = 1; i <= n; i++){ for (int j = i + 1; j <= n; j++) { if (j == i) continue; if (p[j].x - p[j].r <= p[i].x ) { add(j, i); break; } } } for (int i = n; i >= 1; i--){ for (int j = i - 1; j >= 1; j--) { if (j == i) continue; if ( p[i].x <= p[j].x + p[j].r) { add(j, i); break; } } } /* for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i==j) continue; if(p[i].x-p[i].r<=p[j].x&&p[j].x<=p[i].x+p[i].r) add(i,j); }*/ for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) { for (int j = first[i]; j; j = edge[j].nex) { int y = edge[j].ed; if (bl[i] == bl[y]) continue; addc(bl[y], bl[i]); du[bl[i]]++; } } /* for(int i=1;i<=sccnum;i++){ for(int j=0;j<scc[i].size();j++) cout<<scc[i][j]<<" "; cout<<endl; }*/ topsort(); /* for(int i=1;i<=sccnum;i++) cout<<ans[i]<<" ";cout<<endl;*/ for (int i = 1; i <= n; i++) ans1 = (ans1 + 1ll * i * (r[bl[i]]-l[bl[i]]+1)) % mod; printf("%lld", ans1); return 0; }
有点错位，凑合看吧，应该好打。