Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines

題目大意：

給你n個點，分别位于pi。每個點有個爆炸範圍ri和代價ci，花費ci可以引爆某個點，并且pi-ri到pi+ri範圍内的點都會被引爆。q個詢問，每次修改一個點的ci，每次輸出引爆所有店的最小代價。

題解：

學了下線段樹優化建立邊。首先對于這些爆炸關系連邊所點我們可以得到一個DAG，引爆所有點的代價就是所有入度為0的點的代價最小值之和。

那麼這題是區間操作，我們可以用線段樹優化建邊。

先對點安按照pi排序，對1到n建立線段樹，線段樹葉子向着對應的點連邊。

然後每個點的爆炸範圍對應就是一段區間[l,r]。我們将這個點向線段樹對應的線段區間連邊，這樣我們就能得到一張有向圖。

可以發現，這張有向圖上的關系即是所有關系的連邊。對其縮點，得到DAG。

然後對于每個1到n的點dfs，來删除那些全是線段樹點的強連通分量。然後我們對每個入度為0的點維護一個MULTISET，先用ans統計一開始的答案。

每次詢問就是删除插入與詢問最小值了。

附上代碼，樣例見最後注釋

#include<bits/stdc++.h>
using namespace std;
#define exa EXA
struct line
{
	int s,t;
	int next;
}a[10000001];
int head[1200001];
int edge;
inline void add(int s,int t)
{
	a[edge].next=head[s];
	head[s]=edge;
	a[edge].s=s;
	a[edge].t=t;
}
int n;
struct mine
{
	int p,r,c;
	int id;
	bool operator <(mine y) const
	{
		return p<y.p;
	}
}m[200001];
int fx[200001];
inline bool cmp(mine x,mine y)
{
	return x.id<y.id;
}
inline int findlower(int x)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(x<=m[mid].p)
			r=mid-1;
		else
			l=mid+1;
	}
	return l;
}
inline int findupper(int x)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(x<m[mid].p)
			r=mid-1;
		else
			l=mid+1;
	}
	return l;
}
struct tree
{
	int l,r;
	int x;
}tr[800001];
int tot;
inline void build(int p,int l,int r)
{
	tot++;
	tr[p].l=l;
	tr[p].r=r;
	tr[p].x=tot;
	if(l!=r)
	{
		int mid=(l+r)/2;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		edge++;
		add(tr[p].x,tr[p*2].x);
		edge++;
		add(tr[p].x,tr[p*2+1].x);
	}
	else
	{
		edge++;
		add(tr[p].x,tr[p].l);
	}
}
inline void add(int p,int l,int r,int d)
{
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		edge++;
		add(d,tr[p].x);
	}
	else
	{
		int mid=(tr[p].l+tr[p].r)/2;
		if(l<=mid)
			add(p*2,l,r,d);
		if(r>mid)
			add(p*2+1,l,r,d);
	}
}
int scc,cnt;
bool v[1200001];
int s[1200001],top;
int dfn[1200001],low[1200001],belong[1200001];
int indeg[1200001],outdeg[1200001];
inline void tarjan(int d)
{
     int i,x;
     cnt++;
     dfn[d]=cnt;
     low[d]=cnt;
     top++;
     s[top]=d;
     v[d]=true;
     for(i=head[d];i!=0;i=a[i].next)
     {
     	  x=a[i].t;//無向圖記錄fa[d],x==fa[d] continue
          if(dfn[x]==0) 
          {
               tarjan(x);
               low[d]=min(low[d],low[x]);
          }
          else if(v[x]&&low[d]>dfn[x])//v在棧中，修改low[u]
               low[d]=dfn[x];
     }
     if(dfn[d]==low[d])//u為該強連通分量中周遊所成樹的根
     {
          scc++;
          x=s[top];
          top--;
          while(x!=d)
          {    
			   v[x]=false;
               belong[x]=scc;
               x=s[top];
               top--;
          }
          v[x]=false;
          belong[x]=scc;
     }
}
bool vx[1200001],vv[1200001];
inline void dfs(int d)
{
	vv[d]=true;
	vx[belong[d]]=true;
	int i;
	for(i=head[d];i!=0;i=a[i].next)
	{
		int t=a[i].t;
		if(!vv[t])
			dfs(t);
	}
}
inline void count_edge()
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(!vv[i])
			dfs(i);
	}
	for(i=1;i<=edge;i++)
	{
		int d=a[i].s,t=a[i].t;
		if(!vx[belong[d]]||belong[d]==belong[t])
			continue;
		indeg[belong[t]]++;
	}
}
multiset<int> S[1200001];
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	int q;
	scanf("%d%d",&n,&q);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&m[i].p,&m[i].r,&m[i].c);
		m[i].id=i;
	}
	tot=n;
	build(1,1,n);
	sort(m+1,m+1+n);
	for(i=1;i<=n;i++)
	{
		int ll=findlower(m[i].p-m[i].r);
		int rr=findupper(m[i].p+m[i].r);
		rr--;
		add(1,ll,rr,i);
	}
	for(i=1;i<=n;i++)
		fx[m[i].id]=i;
	for(i=1;i<=tot;i++)
	{
		if(!dfn[i])
			tarjan(i);
	}
	count_edge();
	for(i=1;i<=n;i++)
		if(!indeg[belong[i]])
			S[belong[i]].insert(m[i].c);
	long long ans=0;
	multiset<int>::iterator it;
	for(i=1;i<=scc;i++)
	{
		if(!indeg[i])
		{
			it=S[i].begin();
			ans+=(long long)(*it);
		}
	}
	//printf("%lld\n",ans);
	int x,xx;
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&xx);
		x=fx[x];
		if(!indeg[belong[x]])
		{
			it=S[belong[x]].begin();
			ans-=(long long)(*it);
			it=S[belong[x]].find(m[x].c);
			S[belong[x]].erase(it);
			m[x].c=xx;
			S[belong[x]].insert(m[x].c);
			it=S[belong[x]].begin();
			ans+=(long long)(*it);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
4 2
1 1 1
6 3 10
8 2 5
10 2 3
1 1
4 11
*/