P4155 [SCOI2015] 计划

[SCOI2015] 计划 - 洛谷

核心思路

注意到，

可推出，

  表示 战士  走  步到达战士位置。

若可以走到且 r < 终点 则答案 + 

然后再加上自己这个哨兵，和走回自己的一个哨兵即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
int go[N][22];
int n,m;
struct soldier {int id, l, r;
} s[N];
void init(){for(int i = 1, p = i; i <= 2 * n; i++) {while(p <= 2*n&&s[p].l <= s[i].r){p++;}int pos = p-1;go[i][0] = pos;}for(int i = 1; i < 20; i++) {//这两个for循环顺序一定不能换！！！！for(int j = 1; j <= 2 * n; j++) {go[j][i] = go[go[j][i-1]][i-1];}}
}
bool cmp(soldier a,soldier b){return a.l < b.l;
}
int res[1145140];
void find(int k){
//	cout<<k<<endl;int lim = s[k].l + m,ans = 1,p = k;for(int i = 19;i >= 0;i--){if(go[k][i] != 0&& s[go[k][i]].r < lim){ans+=(1 << i);//cout<<k<<endl;k = go[k][i];}}//cout<<endl;res[s[p].id] = ans + 1;
}
int main(){cin>>n>>m;for(int i = 1; i <= n; i++) {cin >> s[i].l >> s[i].r;if(s[i].r < s[i].l)s[i].r += m;s[i].id = i;}sort(s + 1, s + 1 + n, cmp);for(int i = 1; i <= n; i++) {s[i + n] = s[i];s[i + n].l = s[i].l + m;s[i + n].r = s[i].r + m;}init();for(int i = 1; i <= n; i++)find(i);for(int i = 1; i <= n; i++)cout << res[i] << " ";return 0;
}