Problem Analysis

Given a set of bombs positioned on a number line with coordinates and explosion radii, we need to compute the total effect of chain reactions. Each bomb can detonate others within its range, and the propagation continues through connected bombs.

Initial Graph Construction

We first model the problem as a directed graph where each bomb node connects to all bombs within its explosion range. However, this naive approach creates O(n²) edges, which is inefficient for large n.

SCC and Interval Property

Using Tarjan's algorithm, we find Strongly Connnected Components (SCCs) and condense the graph. Crucially, the set of bombs reachable from any bomb forms a continuous interval. This allows us to track minimum and maximum indices instead of full sets.

Monotonic Stack Optimization

Instead of connecting each bomb to all others in its range, we use two monotonic stacks to efficiently find critical connections:

• Left-to-right scan: Connect each bomb to the nearest left bomb that can reach it
• Right-to-left scan: Connect each bomb to nearest right bomb that can reach it

This reduces edge count from O(n²) to O(n) while maintaining reachability information.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 500000;
const int MOD = 1000000007;

struct Explosive {
    long long position;
    long long radius;
};

bool compareExplosives(const Explosive& e1, const Explosive& e2) {
    return e1.position < e2.position;
}

class Graph {
private:
    int edgeCount;
    int head[MAX_N + 1];
    int nextEdge[2 * MAX_N + 1];
    int targetNode[2 * MAX_N + 1];
    
public:
    void initialize() {
        edgeCount = 0;
        memset(head, 0, sizeof(head));
    }
    
    void addConnection(int source, int target) {
        edgeCount++;
        nextEdge[edgeCount] = head[source];
        targetNode[edgeCount] = target;
        head[source] = edgeCount;
    }
};

Graph originalGraph, condensedGraph;
Explosive bombs[MAX_N + 1];
int discoveryTime[MAX_N + 1], lowLink[MAX_N + 1], timeCounter;
int stackNodes[MAX_N], stackTop;
bool inStack[MAX_N + 1];
vector<vector<int>> components;
int componentId[MAX_N + 1];
int minIndex[MAX_N], maxIndex[MAX_N];

void findComponents(int node) {
    discoveryTime[node] = lowLink[node] = ++timeCounter;
    inStack[stackNodes[stackTop++] = node] = true;
    
    for (int i = originalGraph.head[node]; i; i = originalGraph.nextEdge[i]) {
        int neighbor = originalGraph.targetNode[i];
        if (!discoveryTime[neighbor]) {
            findComponents(neighbor);
            lowLink[node] = min(lowLink[node], lowLink[neighbor]);
        } else if (inStack[neighbor]) {
            lowLink[node] = min(lowLink[node], discoveryTime[neighbor]);
        }
    }
    
    if (discoveryTime[node] == lowLink[node]) {
        components.push_back(vector<int>());
        while (true) {
            int current = stackNodes[--stackTop];
            inStack[current] = false;
            components.back().push_back(current);
            componentId[current] = components.size() - 1;
            if (current == node) break;
        }
    }
}

int main() {
    int bombCount;
    cin >> bombCount;
    
    for (int i = 1; i <= bombCount; i++) {
        cin >> bombs[i].position >> bombs[i].radius;
    }
    
    sort(bombs + 1, bombs + bombCount + 1, compareExplosives);
    
    originalGraph.initialize();
    stackTop = 0;
    
    for (int i = 1; i <= bombCount; i++) {
        while (stackTop && bombs[stackNodes[stackTop - 1]].position + 
               bombs[stackNodes[stackTop - 1]].radius < bombs[i].position) {
            stackTop--;
        }
        if (stackTop) {
            originalGraph.addConnection(stackNodes[stackTop - 1], i);
        }
        stackNodes[stackTop++] = i;
    }
    
    stackTop = 0;
    for (int i = bombCount; i >= 1; i--) {
        while (stackTop && bombs[stackNodes[stackTop - 1]].position - 
               bombs[stackNodes[stackTop - 1]].radius > bombs[i].position) {
            stackTop--;
        }
        if (stackTop) {
            originalGraph.addConnection(stackNodes[stackTop - 1], i);
        }
        stackNodes[stackTop++] = i;
    }
    
    for (int i = 1; i <= bombCount; i++) {
        if (!discoveryTime[i]) findComponents(i);
    }
    
    condensedGraph.initialize();
    for (int i = 1; i <= bombCount; i++) {
        for (int j = originalGraph.head[i]; j; j = originalGraph.nextEdge[j]) {
            int target = originalGraph.targetNode[j];
            if (componentId[i] != componentId[target]) {
                condensedGraph.addConnection(componentId[i], componentId[target]);
            }
        }
    }
    
    int result = 0;
    for (int i = 0; i < components.size(); i++) {
        minIndex[i] = INT_MAX;
        maxIndex[i] = INT_MIN;
        int sum = 0;
        
        for (int node : components[i]) {
            minIndex[i] = min(minIndex[i], node);
            maxIndex[i] = max(maxIndex[i], node);
            sum = (sum + node) % MOD;
        }
        
        for (int j = condensedGraph.head[i]; j; j = condensedGraph.nextEdge[j]) {
            int comp = condensedGraph.targetNode[j];
            minIndex[i] = min(minIndex[i], minIndex[comp]);
            maxIndex[i] = max(maxIndex[i], maxIndex[comp]);
        }
        
        result = (result + 1LL * (maxIndex[i] - minIndex[i] + 1) * sum) % MOD;
    }
    
    cout << result;
    return 0;
}