Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines
程序员文章站
2022-05-22 10:50:13
...
题目大意：
给你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
*/