线段树优化建图

有一类经典的问题，之前见过很多次了，好像某一场区域赛的热身赛里就出过：一维数轴上有$n$个炸弹，$x_i,r_i$分别表示第$i$个炸弹的位置和引爆半径，即如果引爆炸弹$i$，那么位置在$[x_i-r_i,x_i+r_i]$范围内的炸弹都会爆炸，并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。

首先一个建图思路是如果$i$能引爆$j$，那么$i$向$j$连一条边，做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是$O(n^2)$的，需要优化。一个显然的观察是，一个点$i$的引爆范围是一段区间（这句是废话），所以是和一个区间的点连边，那么我们把炸弹按位置排序后，$1$到$n$编好号，建线段树，线段树每个点向左右儿子分别连边。如果$i$要向区间$(l,r)$所有点连边的话，就在线段树中将区间$(l,r)$分解成$O(logn)$条线段，这样就转化成了向对应的线段树中的一些点连边，总的边数就是$O(nlogn)$。

来看两道具体的题目：

[bzoj 5017 Snoi2017]炸弹

询问如果把第 $i$ 个炸弹引爆，将引爆多少个炸弹。

线段树优化建图，然后tarjan，答案是从$i$所在的SCC出发，能走到的SCC含有的原炸弹数之和。因为对于每个$i$都要询问，所以这里不能暴力，一个方法是在这个DAG的反图上拓扑序dp一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 2000010
#define M 11000010
const ll mod=1e9+7;
const ll mod2=mod*mod;
struct node
{
    ll x,r;
} a[N];
ll pos[N];
int tot,rt,n;
int ls[N],rs[N];
int e,head[M],last[M],p[N];
int dfn[N],low[N],sta[N],color[N],val[N];
int in[N],q[N];
bool v[N];
int dfstime,num,siz,len;
vector<int> redge[N];
pair<int,int> pr[M];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}
void add(int x,int y)
{
    head[++e]=y;
    last[e]=p[x];
    p[x]=e;
}
void build(int &x,int l,int r)
{
    x=(l==r)?l:(++tot);
    if(l==r) return;
    int mid=l+r>>1;
    build(ls[x],l,mid);
    build(rs[x],mid+1,r);
    add(x,ls[x]);
    add(x,rs[x]);
}
void ins(int x,int l,int r,int L,int R,int y)
{
    if(L<=l && r<=R)
    {
        add(y,x);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) ins(ls[x],l,mid,L,R,y);
    if(mid<R) ins(rs[x],mid+1,r,L,R,y);
}
void tarjan(int x)
{
    int y;
    dfn[x]=low[x]=++dfstime;
    sta[++siz]=x;
    v[x]=true;
    for(int j=p[x];j;j=last[j])
        if(!dfn[y=head[j]])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        ++num;
        do
        {
            y=sta[siz--];
            color[y]=num;
            v[y]=false;
        }while(y!=x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&a[i].x,&a[i].r);
        pos[i]=a[i].x;
    }
    tot=n;
    build(rt,1,n);
    for(int i=1;i<=n;++i)
    {
        int l=lower_bound(pos+1,pos+n+1,a[i].x-a[i].r)-pos;
        int r=upper_bound(pos+1,pos+n+1,a[i].x+a[i].r)-pos-1;
        ins(rt,1,n,l,r,i);
    }
    for(int i=1;i<=tot;++i)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;++i)
        val[color[i]]++;
    for(int x=1;x<=tot;++x)
    {
        for(int j=p[x];j;j=last[j])
        {
            int y=head[j];
            if(color[x]==color[y]) continue;
            pr[++len]=make_pair(color[y],color[x]);
        }
    }
    sort(pr+1,pr+len+1);
    len=unique(pr+1,pr+len+1)-pr-1;
    for(int i=1;i<=len;++i)
    {
        redge[pr[i].first].push_back(pr[i].second);
        ++in[pr[i].second];
    }
    int l=0,r=0;
    for(int i=1;i<=num;++i)
        if(!in[i])
            q[r++]=i;
    while(l!=r)
    {
        int x=q[l++];
        for(int i=0;i<redge[x].size();++i)
        {
            int y=redge[x][i];
            val[y]+=val[x];
            if((--in[y])==0) q[r++]=y;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=1LL*i*val[color[i]];
        if(ans>=mod2) ans-=mod2;
    }
    ans%=mod;
    printf("%d\n",ans);
}

Petrozavodsk Winter-2018. Carnegie Mellon U Contest A Mines

现在每个炸弹多了一个初始的引爆费用，因为连锁发生的爆炸是免费的。有$q$次修改，每次修改一个炸弹的费用，对于每次修改都要查询当前要引爆所有炸弹的最小花费。

前面的操作都一样，首先一个显然的想法是只要引爆DAG中所有入度为$0$的SCC里的费用最小的炸弹。然后有个致命的问题是，入度为$0$的SCC可能不含有原$1$到$n$号点，所以需要做拓扑排序删掉没用的点，之后对于每次询问用set维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define NN 200010
#define N 800010
#define M 16000010
#define rep(i,l,r) for(int i=l;i<=r;++i)
struct node
{
    int x,r,c,o;
} a[NN];
int h[NN],pos[NN],ls[N],rs[N];
int n,tot,m,rt,dfstime,siz,num;
int e,head[M],last[M],p[N];
int dfn[N],low[N],sta[N],color[N];
int in[N],q[N];
bool v[N],ok[N];
vector<int> edge[N];
multiset<int> st[N];
bool cmp(const node &a,const node &b)
{
    return a.x<b.x;
}

void add(int x,int y)
{
    head[++e]=y;
    last[e]=p[x];
    p[x]=e;
}
void tarjan(int x)
{
    int y;
    dfn[x]=low[x]=++dfstime;
    sta[++siz]=x;
    v[x]=true;
    for(int j=p[x];j;j=last[j])
        if(!dfn[y=head[j]])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[x],dfn[y]);
    if(low[x]==dfn[x])
    {
        ++num;
        do
        {
            y=sta[siz--];
            color[y]=num;
            v[y]=false;
        }while(y!=x);
    }
}
void build(int &x,int l,int r)
{
    x=(l==r)?l:(++tot);
    if(l==r) return;
    int mid=l+r>>1;
    build(ls[x],l,mid);
    build(rs[x],mid+1,r);
    add(x,ls[x]);
    add(x,rs[x]);
}
void ins(int x,int l,int r,int L,int R,int y)
{
    if(L<=l && r<=R)
    {
        add(y,x);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) ins(ls[x],l,mid,L,R,y);
    if(mid<R) ins(rs[x],mid+1,r,L,R,y);
}
int main()
{
    #ifdef SK
    freopen("input.txt","r",stdin);
    #endif // SK
    scanf("%d%d",&n,&m);
    rep(i,1,n)
    {
        scanf("%d%d%d",&a[i].x,&a[i].r,&a[i].c);
        a[i].o=i;
    }
    sort(a+1,a+n+1,cmp);
    rep(i,1,n) h[i]=a[i].x,pos[a[i].o]=i;
    tot=n;
    build(rt,1,n);
    rep(i,1,n)
    {
        int l=lower_bound(h+1,h+n+1,a[i].x-a[i].r)-h;
        int r=upper_bound(h+1,h+n+1,a[i].x+a[i].r)-h-1;
        ins(rt,1,n,l,r,i);
    }
    rep(i,1,tot)
        if(!dfn[i])
            tarjan(i);
    rep(i,1,n) ok[color[i]]=true;
    for(int x=1;x<=tot;++x)
    {
        for(int j=p[x];j;j=last[j])
        {
            int y=head[j];
            int xx=color[x],yy=color[y];
            if(xx==yy) continue;
            edge[xx].push_back(yy);
            ++in[yy];
        }
    }
    int l=0,r=0;
    rep(i,1,num)
        if(!in[i] && !ok[i])
            q[r++]=i;
    while(l!=r)
    {
        int x=q[l++];
        for(auto &y:edge[x])
        {
            --in[y];
            if(!in[y] && !ok[y]) q[r++]=y;
        }
    }

    rep(i,1,n)
        if(!in[color[i]])
            st[color[i]].insert(a[i].c);

    ll ans=0;
    rep(i,1,num)
        if(ok[i] && !in[i] && !st[i].empty())
            ans+=*st[i].begin();

    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x=pos[x];
        if(!in[color[x]])
        {
            ans-=*st[color[x]].begin();
            auto it=st[color[x]].find(a[x].c);
            st[color[x]].erase(it);
            a[x].c=y;
            st[color[x]].insert(a[x].c);
            ans+=*st[color[x]].begin();
        }
        printf("%lld\n",ans);
    }
    return 0;
}