86分,WA,线段树+Tarjan+DAG上DP 求助
查看原帖
86分,WA,线段树+Tarjan+DAG上DP 求助
160701
Azazеl楼主2020/11/5 22:00

RT,已经跟题解进行了 肉眼对拍和 对拍,没找出问题,第一、二个点WA,已经处理了 xx 不是升序的问题。

#include <bits/stdc++.h>
#define ll long long 
const ll WY=1e9+7;
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    x*=f;
}
template<typename T>void print(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const ll MAXN=6e5+5;
ll x[MAXN<<2],rr[MAXN<<2],id[MAXN<<2];
ll NodeNum;
struct Interval{
	ll l,r;
	Interval(){l=0,r=0;}
	Interval(ll L,ll R){l=L,r=R;}
}P[MAXN<<2];
map <ll,bool> M[MAXN<<2];
vector <ll> G[MAXN<<2],G_[MAXN<<2];
ll L[MAXN<<2],R[MAXN<<2];
struct SegmentTree{
	#define ls p<<1
	#define rs p<<1|1
	#define lson ls,l,mid
	#define rson rs,mid+1,r
	void build(ll p,ll l,ll r)
	{
		P[p]=Interval(l,r);
		NodeNum=max(NodeNum,p);
		if(l==r)
		{
			id[l]=p;
			return;
		}
		ll mid=(l+r)>>1;
		build(lson);build(rson);
		G[p].push_back(ls);
		G[p].push_back(rs);
	}
	void Add(ll p,ll l,ll r,ll lx,ll rx,ll From)
	{
		if(lx<=l&&r<=rx)
		{
			if(p==From) return;
			G[From].push_back(p);
			return;
		}
		ll mid=(l+r)>>1;
		if(lx<=mid) Add(lson,lx,rx,From);
		if(rx>mid)  Add(rson,lx,rx,From);
	}
}tr;
stack<ll> S;
bool InStack[MAXN<<2];
ll dfn[MAXN<<2],low[MAXN<<2],Times,tot;
ll belong[MAXN<<2];
void Tarjan(ll u)
{
	dfn[u]=low[u]=++Times;
	S.push(u);
	InStack[u]=true;
	for(ll i=0;i<(ll)G[u].size();i++)
	{
		ll v=G[u][i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(InStack[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		ll t=-1;
		tot++;
		while(t!=u)
		{
			t=S.top();
			S.pop();
			InStack[u]=false;
			belong[t]=tot;
			L[tot]=min(L[tot],P[t].l);
			R[tot]=max(R[tot],P[t].r);
		}
	}
}
bool vis[MAXN<<2];
void dfs(int u){ //最后一遍 dfs 更新
	vis[u] = true;
	int v,l = G_[u].size();
	for(int i=0;i!=l;++i){
		v = G_[u][i];
		if(vis[v]){
			L[u] = min(L[u],L[v]);
			R[u] = max(R[u],R[v]);
			continue;
		}
		dfs(v);
		L[u] = min(L[u],L[v]);
		R[u] = max(R[u],R[v]);
	}
}
struct node{
	ll x,r;
}Op[MAXN<<2];
inline bool cmp(node X,node Y)
{
	return X.x<Y.x;
}
int main() {
//	freopen("Bomb1.in","r",stdin);
//	freopen("Bomb1.out","w",stdout);
	memset(L,0x3f,sizeof(L));
	ll n;
	read(n);
	for(ll i=1;i<=n;i++)
	{
		read(Op[i].x);
		read(Op[i].r);
	}
	Op[n+1].x=0x3f3f3f3f3f3f3f3fll;
	sort(Op+1,Op+2+n,cmp);
	for(int i=1;i<=n+1;i++) x[i]=Op[i].x;
	tr.build(1,1,n);
	for(ll i=1,LL,RR;i<=n;i++)
	{
		if(!Op[i].r) continue;
		LL=lower_bound(x+1,x+1+n,x[i]-Op[i].r)-x;
		RR=upper_bound(x+1,x+1+n,x[i]+Op[i].r)-x-1;
		tr.Add(1,1,n,LL,RR,id[i]);
		P[id[i]]=Interval(LL,RR);
	}
	Tarjan(1);
	for(ll u=1;u<=NodeNum;u++)
	{
		for(ll i=0;i<(ll)G[u].size();i++)
		{
			ll v=G[u][i];
			ll X=belong[u],y=belong[v];
			if(X==y||M[X][y]) continue;
			G_[X].push_back(y);
			M[X][y]=true;
		}
	}
	ll ans=0;
	for(ll i=1;i<=tot;i++) if(!vis[i]) dfs(i);
	for(ll i=1;i<=n;i++)
	{
		ll tmp=0;
		ll X=belong[id[i]];
		tmp=R[X]-L[X]+1;
		ans=(ans+tmp*i%WY)%WY;
	}
	printf("%lld",ans);
	return 0;
}
2020/11/5 22:00
加载中...