Petrozavodsk Winter-2018. Carnegie Mellon U Contest. A. Mines 线段树建图+强连通分量

Problem A. Mines
Input file: standard input
Output file: standard output
Time limit: 10 seconds

There are N mines on the number line. Mine i is at position pi and has an explosion radius ri. It initially
costs ci to detonate. If mine i is detonated, an explosion occurs on interval [pi - ri; pi + ri] and all mines
in that interval (inclusive of the endpoints) are detonated for free, setting off a chain reaction. You need
to process Q operations of the form (m; c): Change the cost of detonating mine m to c. Output the
minimum cost required to detonate all mines after each change. Note that each change is permanent.

Input

The first line contains integers N and Q (1 ≤ N; Q ≤ 200 000). The next N lines contain information on the mines. The i-th of these lines contains integers pi, ri and ci (1 ≤ pi; ri; ci ≤ 109). The next Q lines each contains space separated integers m and c (1 ≤ m ≤ N, 1 ≤ c ≤ 109).

Output
Output Q lines. The i-th line should contain the minimum cost required to detonate all mines after the
i-th operation

Example

standard input	standard output
4 2 1 1 1 6 3 10 8 2 5 10 2 3 1 1 4 11	4 6

 

 

 

n个矿井分布在一维坐标轴上，分别有不同的爆炸半径和爆炸成本。花费Ci引爆其中一个会引起连锁反应，现在Q次操作，每次改变一个矿井的花费，要求对于每次操作输出最少花费多少引爆所有矿井。

 

建图很容易想，但是边数太多。我们可以把点先按位置排序，再用线段树建图，树上每个点代表一段连续区间所有的点。这样，边数被压缩到nlogn的级别。接着就好求了，只要把图缩点之后，找到DAG当中入度为0的点，在这些点代表的强连通分量当中取一个花费最小的点就好。至于Q次操作，可以对这些强连通分量当中的所有点以及花费用set维护。

时间复杂度O(nlogn)

 

双向dfs求强连通分量的过程：

1.以任意一个点为源点，进行dfs，并将记录经过点的时间戳，时间戳逐渐增加。 
2.进行dfs后，将图中的边的方向反向。寻找时间戳最小的点为源点（就是上面源点）进行dfs。这时，它所能达到的点集就是一个连通分量。并记录搜索过的点 
3.在没有搜索过的点中以时间戳最小的点为源点，继续dfs，搜索结果同上 
4.不断重复3，直到所有点都搜索过。 

 

顺便吐槽一下CSDN,新编辑器居然不能改字体大小了，很多功能找不到，越来越烂了，是逼我转Markdown吗

 

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define pb push_back 
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int,int> pp;
const int maxn=1000005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int l[maxn],r[maxn],q[maxn],f[maxn];
bool vis[maxn],z[maxn];
pp b[maxn];
set<pp> s[maxn];
vector<int> v[maxn],vi[maxn],v1[maxn];
int n,num,cnt,c;

struct node{
	int p,r,c;
};
node a[maxn];

int findl(int pos) {
	int l=1,r=n,mid,ans=-1;
	while (l<=r) {
		mid=(l+r)/2;
		if (b[mid].first<pos) l=mid+1; else ans=mid,r=mid-1;
	}
	return ans;
}
int findr(int pos) {
	int l=1,r=n,mid,ans=-1;
	while (l<=r) {
		mid=(l+r)/2;
		if (b[mid].first>pos) r=mid-1; else ans=mid,l=mid+1;
	}
	return ans;
}

void addedge(int x,int y) {
	v[x].pb(y);
	v1[y].pb(x);
}

void newedge(int x,int y) {
	vi[x].pb(y);
//	cout << x << ' ' << y << endl;
}

int build(int lc,int rc) {
	if (lc==rc) {
		return b[lc].second;
	}
	int now=++num;
	l[now]=build(lc,(lc+rc)/2);
	r[now]=build((lc+rc)/2+1,rc);
	addedge(now,l[now]);
	addedge(now,r[now]);
	return now;
}

void buildedge(int now,int lc,int rc,int f,int nl,int nr) {
	if (nl>=lc&&rc>=nr) {
		addedge(f,now);
		return;
	}
	int mid=(nl+nr)/2;
	if (lc<=mid) buildedge(l[now],lc,rc,f,nl,mid);
	if (rc>mid) buildedge(r[now],lc,rc,f,mid+1,nr);
}

void dfs1(int now) {
	vis[now]=1;
	int size=v[now].size();
	for (int i=0;i<size;i++) {
		if (!vis[v[now][i]]) dfs1(v[now][i]);
	}
	q[++cnt]=now;
}

void dfs2(int now) {
	vis[now]=0;f[now]=c;
	int size=v1[now].size();
	for (int i=0;i<size;i++) {
		if (vis[v1[now][i]]) dfs2(v1[now][i]);
	}
}

void dfs3(int now) {
	z[now]=1;
	int size=vi[now].size();
	for (int i=0;i<size;i++) {
		if (!z[vi[now][i]]) dfs3(vi[now][i]);
	}
}

int main() {
	int qn,i,j;
	scanf("%d%d",&n,&qn);
	num=n;
	for (i=1;i<=n;i++) {
		scanf("%d%d%d",&a[i].p,&a[i].r,&a[i].c);
		b[i]=pp(a[i].p,i);
	}
	sort(b+1,b+n+1);
	int root=build(1,n);
	for (i=1;i<=n;i++) {
		int ll=findl(a[i].p-a[i].r);
		int rr=findr(a[i].p+a[i].r);
		buildedge(root,ll,rr,i,1,n);
	}
	cnt=c=0;
	for (i=1;i<=num;i++) 
		if (!vis[i]) dfs1(i);
	for (i=num;i;i--) 
		if (vis[q[i]]) c++,dfs2(q[i]);
	for (i=1;i<=num;i++) {
		int size=v[i].size();
		for (j=0;j<size;j++) {
			if (f[i]!=f[v[i][j]]) newedge(f[i],f[v[i][j]]);
		}
	}
	for (i=1;i<=n;i++) {
		if (!vis[f[i]]){
			vis[f[i]]=1;
			int size=vi[f[i]].size();
			for (j=0;j<size;j++) {
				if (!z[vi[f[i]][j]]) dfs3(vi[f[i]][j]);
			}
		}
	}
	for (i=1;i<=n;i++) 
		if (!z[f[i]]) s[f[i]].insert(pp(a[i].c,i));
	ll ans=0;
	for (i=1;i<=c;i++) 
		if (!z[i]&&!s[i].empty()) ans+=(ll)s[i].begin()->first;
	int x,y;
	for (i=1;i<=qn;i++) {
		scanf("%d%d",&x,&y);
		if (z[f[x]]) {
			printf("%lld\n",ans);
			continue;
		}
		ans-=(ll)s[f[x]].begin()->first;
		s[f[x]].erase(pp(a[x].c,x));
		a[x].c=y;
		s[f[x]].insert(pp(y,x));
		ans+=(ll)s[f[x]].begin()->first;
		printf("%lld\n",ans);
	}
	return 0;
}