Petrozavodsk Winter 2018 - A. Mines - 세그먼트 트리 최적화 설계도, 강연통 분량 축소점,DP

제목: 1차원 수축에 nnn개의 천둥이 있다.제 i i i 개 천둥 위치 p i pi pi​. 소비 c i cici의 대가로 ii i개의 천둥을 터뜨리고 구간 [pi-3-ri, pi+ri] [p i-r i, p i+r i] [pi-3-ri, pi+ri] 범위의 천둥을 모두 터뜨려 연쇄반응을 일으키며 별도의 대가가 필요하지 않습니다.현재 qqq회 수정, 매번 한 개의 뇌를 수정하는 비용, 그리고 모든 뇌가 폭발할 수 있는 최소 비용이 얼마인지 문의합니다.

1 ≤ n , q ≤ 200 , 000 1\le n,q\le 200,000 1≤n,q≤200,000

1 ≤ p i , r i , c i ≤ 1 , 000 , 000 , 000 1\le p_i,r_i,c_i\le 1,000,000,000 1≤pi​,ri​,ci​≤1,000,000,000

문제풀이: 한 그루의 나무 한 그루를 짓고 각 아버지의 노드가 좌우 아들에게 각각 한 줄기 방향이 있다.그리고 천둥 하나하나를 매거하여, pi p 에서i pi가 있는 잎사귀 노드는 [p i -3 r i, p i + r i] [p i-r i, p i + r i] [pi -3 ri, pi +ri]에 대응하는 노드를 연결하고 tarjan은 scc를 한 번 구한다.잎 노드를 포함하는 scc에서 도착할 수 있는 모든 scc를 삭제하고 나머지 잎을 포함하는 scc의 최소값의 합이 답입니다.수정은 scc마다 멀티셋을 유지할 수 있습니다.시간 복잡도 O(n log ⁡ n)\mathcal{O} (n\log{n}) O(nlogn).
코드:

#include 
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int maxm = maxn << 2;
vector g[maxm], h[maxm];
int dfn[maxm], low[maxm], belong[maxm], scc, cnt;
bool vis[maxm];
stack s;
void tarjan(int u) {
    low[u] = dfn[u] = ++cnt;
    s.push(u);
    vis[u] = 1;
    for (int v: g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++scc;
        int v;
        do {
            v = s.top();
            s.pop();
            vis[v] = 0;
            belong[v] = scc;
        } while (u != v);
    }
}
int id[maxn];
struct SegmentTree {
#define ls (rt<<1)
#define rs (rt<<1|1)
    void build(int l, int r, int rt) {
        if (l == r) {
            id[l] = rt;
            return;
        }
        int m = (l + r) / 2;
        g[rt].push_back(ls);
        g[rt].push_back(rs);
        build(l, m, ls);
        build(m+1, r, rs);
    }

    void query(int l, int r, int p, int L, int R, int rt) {
        if (l <= L && R <= r) {
            g[p].push_back(rt);
            return;
        }
        int m = (L + R) / 2;
        if (l <= m) query(l, r, p, L, m, ls);
        if (r > m) query(l, r, p, m+1, R, rs);
    }
} T;
struct node {
    int p, r, c;
    friend bool operator< (const node& x, const node& y) {
        return x.p < y.p;
    }
} a[maxn];
int rk[maxn], in[maxm];
vector> dx;
multiset ms[maxm];
bool ins[maxm];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a[i].p, &a[i].r, &a[i].c);
        dx.push_back({a[i].p, i});
    }
    sort(dx.begin(), dx.end());
    T.build(1, n, 1);
    for (int i = 1; i <= n; i++) {
        rk[i] = lower_bound(dx.begin(), dx.end(), make_pair(a[i].p, i)) - dx.begin() + 1;
        int l = lower_bound(dx.begin(), dx.end(), make_pair(a[i].p - a[i].r, 0)) - dx.begin() + 1;
        int r = lower_bound(dx.begin(), dx.end(), make_pair(a[i].p + a[i].r + 1, 0)) - dx.begin();
        T.query(l, r, id[rk[i]], 1, n, 1);
    }
    int m = 4 * n;
    for (int i = 1; i <= m; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= scc; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        vis[belong[id[rk[i]]]] = 1;
        ms[belong[id[rk[i]]]].insert(a[i].c);
    }
    queue Q;
    for (int u = 1; u <= m; u++) {
        for (int v: g[u]) {
            if (belong[u] != belong[v]) {
                h[belong[u]].push_back(belong[v]);
                if (vis[belong[u]]) {
                    ++in[belong[v]];
                    if (!vis[belong[v]] && !ins[belong[v]]) {
                        Q.push(belong[v]);
                        ins[v] = 1;
                    }
                }
            }
        }
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v: h[u]) {
            in[v] += in[u];
            if (!ins[v]) {
                Q.push(v);
                ins[v] = 1;
            }
        }
        ins[u] = 0;
    }
    ll sum = 0;
    for (int i = 1; i <= scc; i++) {
        if (vis[i] && in[i] == 0) sum += *ms[i].begin(); 
    }
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (!in[belong[id[rk[x]]]]) {
            sum -= *ms[belong[id[rk[x]]]].begin();
            auto it = ms[belong[id[rk[x]]]].find(a[x].c);
            ms[belong[id[rk[x]]]].erase(it);
            ms[belong[id[rk[x]]]].insert(y);
            sum += *ms[belong[id[rk[x]]]].begin();
            a[x].c = y;
        }
        printf("%lld
", sum);
    }
    return 0;
}