P5025 - [SNOI 2017] 폭탄 [tarjan, 선분 수 최적화 건설 도]
제목 링크:https://www.luogu.com.cn/problem/P5025
제목 의 대의
n n 개의 폭탄 은 각각 x x x 위치 에 있 고 범 위 는 r r 이다.정의 f i fi fi 는 제 i 개 폭탄 폭발 이 연쇄 할 수 있 는 폭탄 수 를 나타 내 고 > i = 1 n f i * 8727 ° i \ sum{i=1}^nf_i*i i=1∑nfi∗i
문제 풀이 의 사고 방향.
모든 폭탄 이 터 질 수 있 는 폭탄 을 가장자리 에 연결 한 후, 모든 강 한 연결 분량 간 에 서로 폭발 할 수 있 습 니 다. 그리고 t a r j a n tarjan tarjan 시 이 강 한 연결 분량 내의 폭탄 폭발 범 위 를 통계 합 니 다. l i, r i li,r_i li,ri。그리고 df s dfs dfs 로 D A G DAG DAG 에서 업데이트 하면 됩 니 다.
그러나 이렇게 만 든 사 이 드 는 n 2 n ^ 2 n2 등급 으로 본 문 제 를 통과 할 수 없습니다. 왜냐하면 만 든 사 이 드 는 모두 한 구간 에 있 기 때문에 선분 나무 로 사 이 드 를 최적화 시 킵 니 다. 각 노드 는 이 노드 가 연 결 된 구간 점 으로 통 할 수 있 음 을 나타 내 고 n log * 8289 ° n n \ log n nlogn 의 등급 으로 최적화 합 니 다.
c o d e code code
#include
#include
#include
#include
#define ll long long
using namespace std;
const ll N=2e6+10,XJQ=1e9+7;
struct node{
ll to,from,next;
}a[N*15];
ll n,tot,num,cnt,ans;
ll lso[N],rso[N],dfn[N],low[N];
ll l[N],r[N],ls[N],fa[N],w[N],rr[N];
stack<int> S;
bool v[N];
void addl(ll x,ll y){
a[++tot].to=y;
a[tot].from=x;
a[tot].next=ls[x];
ls[x]=tot;
return;
}
ll build(ll x,ll l,ll r){
if(l==r)return l;
if(!x)x=++cnt;
ll mid=(l+r)>>1;
lso[x]=build(lso[x],l,mid);
rso[x]=build(rso[x],mid+1,r);
addl(x,lso[x]);addl(x,rso[x]);
return x;
}
void change(ll x,ll L,ll R,ll l,ll r,ll pos){
if(L==l&&R==r)
{addl(pos,x);return;}
ll mid=(L+R)>>1;
if(r<=mid)change(lso[x],L,mid,l,r,pos);
else if(l>mid)change(rso[x],mid+1,R,l,r,pos);
else change(lso[x],L,mid,l,mid,pos),
change(rso[x],mid+1,R,mid+1,r,pos);
return;
}
void tarjan(ll x){
dfn[x]=low[x]=++num;
v[x]=1;S.push(x);
for(ll i=ls[x];i;i=a[i].next){
ll y=a[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(v[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
ll y;
do{
y=S.top();
v[y]=0;fa[y]=x;
l[x]=min(l[x],l[y]);
r[x]=max(r[x],r[y]);
S.pop();
}while(x!=y);
}
return;
}
void dfs(ll x){
v[x]=1;
for(ll i=ls[x];i;i=a[i].next){
ll y=a[i].to;
if(!v[y])dfs(y);
l[x]=min(l[x],l[y]);
r[x]=max(r[x],r[y]);
}
return;
}
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld%lld",&w[i],&rr[i]);
cnt=n;build(0,1,n);
memset(l,127,sizeof(l));
w[n+1]=2147483647;
for(ll i=1;i<=n;i++){
ll L=lower_bound(w+1,w+1+n,w[i]-rr[i])-w;
ll R=upper_bound(w+1,w+1+n,w[i]+rr[i])-w-1;
change(n+1,1,n,L,R,i);l[i]=L;r[i]=R;
}
for(ll i=1;i<=cnt;i++)
if(!dfn[i])tarjan(i);
ll TOT=tot;tot=0;
memset(ls,0,sizeof(ls));
for(ll i=1;i<=TOT;i++){
ll x=a[i].from,y=a[i].to;
if(fa[x]==fa[y])continue;
addl(fa[a[i].from],fa[a[i].to]);
}
memset(v,0,sizeof(v));
for(ll i=1;i<=cnt;i++)
if(fa[i]==i)dfs(i);
for(ll i=1;i<=n;i++)
ans=(ans+(r[fa[i]]-l[fa[i]]+1)*i%XJQ)%XJQ;
printf("%lld",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.