Description
Input
Output
Sample Input
2 5
4 7
6 1
7 3
Sample Output
HINT
n≤2×10^5,M< 10^9,1≤Ci,Di≤M
题解:遇到环的题,显然要将环倍长一遍变成链做。
先排序,然后对于每个战士,他一定是传给他能传到的,右端点最远的战士,所以可以用双指针法搞定。
然后用倍增的思想,用to[i][j]表示i往后传2^j次会传给谁,查询时像倍增求lca一样查询就行了。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=200010; struct node { int a,b,org; node(){} node(int x,int y,int z){a=x,b=y,org=z;} }p[maxn<<1]; int n,m,tot; int to[20][maxn<<1],ans[maxn]; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } bool cmp(const node &a,const node &b) { return a.b<b.b; } int main() { n=rd(),m=rd(); int i,j,a,b; for(i=1;i<=n;i++) { a=rd(),b=rd(); if(a>b) p[++tot]=node(a,b+m,i),p[++tot]=node(a+m,b+m+m,i); //这里把后半句去掉则会WA,不明觉厉 else p[++tot]=node(a,b,i),p[++tot]=node(a+m,b+m,i); } sort(p+1,p+tot+1,cmp); for(i=j=1;i<=tot;i++) { for(;j<tot&&p[j+1].a<=p[i].b;j++); to[0][i]=(i==j)?0:j; } for(j=1;(1<<j)<=tot;j++) for(i=1;i<=tot;i++) to[j][i]=to[j-1][to[j-1][i]]; for(i=1;i<=tot;i++) { if(p[i].a>m) continue; a=i,b=0; for(j=19;j>=0;j--) if(to[j][a]&&p[to[j][a]].b<p[i].a+m) a=to[j][a],b+=(1<<j); a=to[0][a],b++; ans[p[i].org]=b+(p[i].org!=p[a].org); } for(i=1;i<=n;i++) { printf("%d",ans[i]); if(i<n) printf(" "); } return 0; }