[SCOI2015] 計劃 - 洛谷

核心思路

注意到，

可推出，

? 表示 戰(zhàn)士 ?走??步到達戰(zhàn)士位置。

若可以走到且 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循環(huán)順序一定不能換！！！！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;
}