树上倍增
首先剖环成2倍长的链
对于每一个士兵求他的下一个士兵应该选哪一个，记录进Next数组
注意此时Next数组形成了一棵树，然后树上倍增就可以了
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,m,Next[400005],cnt,ans[200005],fa[400005][20];
struct Soldier{
long long l,r;
int id;
friend bool operator<(Soldier A,Soldier B){return A.l<B.l;}
}sol[400005];
int main(){
freopen("4444.in","r",stdin);
freopen("4444.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
int xl,xr;
scanf("%d %d",&xl,&xr);
if(xl<xr){
sol[++cnt].l=xl;sol[cnt].r=xr;
sol[cnt].id=i;
sol[++cnt].l=xl+m;sol[cnt].r=xr+m;
}
else {
sol[++cnt].l=xl;sol[cnt].r=xr+m;
sol[cnt].id=i;
sol[++cnt].l=xl+m;sol[cnt].r=xr+m+m;
}
}
sol[0].r=21000000000000000ll;
sort(sol+1,sol+cnt+1);
int j=0;
for(int i=1;i<=cnt;i++){
while(j<=cnt && sol[j].l<=sol[i].r)j++;
Next[i]=j-1;
}
for(int i=cnt-1;i>=1;i--){
fa[i][0]=Next[i];
for(j=1;j<=19;j++)fa[i][j]=fa[fa[i][j-1]][j-1];
if(sol[i].id){
int tp=i;
for(j=19;j>=0;j--){if(sol[fa[tp][j]].r-sol[i].l<m){ans[sol[i].id]+=1<<j;tp=fa[tp][j];}}
ans[sol[i].id]+=2;
}
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
评论 (0)
