【SNOI2017 DAY1】炸弹

题意：P5024
思路：首先\(O(n^2)\)向能炸到的点连边，所以能到达的点的个数就是能到达的点的个数。然后显然要缩点+拓扑排序（我写的记搜）。

然后再写一个线段树优化建图。

然后就WA了，我想了很久才明白我的记搜有问题，一个点可能用来更新另一个点多次。我看了下题解，题解很nice,也很好写，就维护一个联通分量能到的范围[左右端点]（此题的性质保证能到的点集是一个子段)。
代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e6+5;

const int M=4e7+5;

struct seg {int l,r;}T[N];

struct node {ll p,r;}a[N];

bool cmp(node u,node v) {return u.p<v.p;}

bool In_s[N];

ll sum[N],mod=1e9+7,mp[N],cnt[N],ans[N];

int L[N],R[N],mx[N],mn[N],r[N],o[N],tim,Ecnt,In[N],Bl[N],mark[N],SCC,mxx,lf[N],Time,low[N],dfn[N],st[N],tp,n,nxt[M],to[M],head[N],ecnt;

void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}

void Build(int x,int l,int r) {

	T[x]=(seg){l,r},mxx=max(mxx,x);

	if(l==r) {lf[l]=x,mark[x]=l;return;}

	int mid=(l+r)>>1,ls=x<<1,rs=x<<1|1;

	add_edge(x,ls),add_edge(x,rs);

	Build(ls,l,mid),Build(rs,mid+1,r);

}

void Add(int x,int u,int l,int r) {

	if(l<=T[x].l&&T[x].r<=r) {add_edge(lf[u],x);return;}

	int mid=(T[x].l+T[x].r)>>1;

	if(l<=mid)Add(x<<1,u,l,r);

	if(r>mid)Add(x<<1|1,u,l,r);

}

void Tarjan(int u) {

	dfn[u]=low[u]=++Time,In_s[u]=1;

	st[++tp]=u;

	for(int i=head[u];i;i=nxt[i]) {

		int v=to[i];

		if(!dfn[v]) {

			Tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else if(In_s[v]) low[u]=min(low[u],dfn[v]);

	}

	if(low[u]==dfn[u]) {

		int v;

		SCC++;

		L[SCC]=1e9;

		do {

			v=st[tp--],L[SCC]=min(L[SCC],T[v].l),R[SCC]=max(R[SCC],T[v].r),sum[SCC]+=mark[v],Bl[v]=SCC,In_s[v]=0;

		}while(u!=v);

	}

}

vector<int> G[N];

void dfs(int u) {

	if(ans[u]) return;

	ans[u]=1;

	for(int i=0;i<G[u].size();i++) {

		int v=G[u][i];

		dfs(v);

		L[u]=min(L[v],L[u]),R[u]=max(R[u],R[v]);

	}

}

int main() {

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%lld%lld",&a[i].p,&a[i].r);

	}

	Build(1,1,n);

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++) mp[i]=a[i].p;

	for(int i=1;i<=n;i++) {

		int l=lower_bound(mp+1,mp+1+i,a[i].p-a[i].r)-mp;

		int r=upper_bound(mp+1+i,mp+1+n,a[i].p+a[i].r)-mp-1;

		Add(1,i,l,r);

	}

	Tarjan(1);

	n=mxx;

	for(int u=1;u<=n;u++) {

		for(int i=head[u];i;i=nxt[i]) {

			int v=to[i];

			if(Bl[u]!=Bl[v])G[Bl[u]].push_back(Bl[v]),In[Bl[v]]++;

		}

	}

	for(int i=1;i<=SCC;i++) {

		if(!ans[i]&&!In[i]) {

			dfs(i);

		}

	}

	ll res=0;

	for(int i=1;i<=SCC;i++) {

//		printf("%d %d\n",L[i],R[i]);

		res=(res+1ll*sum[i]%mod*(R[i]-L[i]+1)%mod)%mod;

	}

	printf("%lld",res);

	return 0;

}

巴特西

【SNOI2017 DAY1】炸弹

最新文章

热门文章