省流：不会做可以去看标签，做法全在标签里，一个不多一个不少
题目传送门
很容易想到开个结构体存每个士兵的奔袭区间和初始编号，顺便把排序函数写里面
struct node {int idx, l, r;bool operator < (const node &b) const { // const 不 const 的不重要，要加就加两个，不加就都别加return l < b.l;}
} a[maxn << 1];
这题是个环，可以复制一遍在原数组后面方便操作。
就是
n2 = n;
for (int i = 1; i <= n; i++){++n2;a[n2] = a[i]; // 这个是整体赋值，实在不行你可以 a[n2].idx = a[i].idxa[n2].l = a[i].l + m;a[n2].r = a[i].r + m;
}
这个 n2 看不懂的话可以这么写：
for (int i = 1; i <= n; i++){a[i + n] = a[i];a[i + n].l = a[i].l + m;a[i + n].r = a[i].r + m;
}
然后我们开始倍增，类似 DP 一样
\[go[i][j] = go[go[i][j - 1]][j - 1]
\]
于是：
void init() {int nxt = 1;for (int i = 1; i <= n * 2; i++) {while (nxt <= n * 2 && a[nxt].l <= a[i].r)nxt++;go[i][0] = nxt - 1;} // 类似 DP 的初始化for (int i = 1; (1 << i) <= n; i++)for (int j = 1; j <= n * 2; j++)go[j][i] = go[go[j][i - 1]][i - 1];
}
求答案：
void getans(int x) {int len = a[x].l + m, cur = x, ans = 1;for (int i = log2(maxn); i >= 0; i--) {int pos = go[cur][i];if (pos && a[pos].r < len)ans += (1 << i), cur = pos;}res[a[x].idx] = ans + 1;
}
最后整合到一起就行了。
code
/*
1.MLE?
2.array size enough?
3.long long?
4.overflow long long?
5.multiple task cleaned?
6.freopen?
7.TLE?
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <deque>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <list>
#include <array>
#include <iterator>
#include <cmath>
#include <new>
#include <random>
#include <cfloat>
#include <cstdlib>
#include <climits>
#include <numeric>
#include <complex>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <future>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <cassert>
#include <stack>
#include <cctype>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 200005;int n, m;int go[maxn << 1][20], res[maxn];struct node {int idx, l, r;bool operator < (const node &b) const {return l < b.l;}
} a[maxn << 1];void init() {int nxt = 1;for (int i = 1; i <= n * 2; i++) {while (nxt <= n * 2 && a[nxt].l <= a[i].r)nxt++;go[i][0] = nxt - 1;}for (int i = 1; (1 << i) <= n; i++)for (int j = 1; j <= n * 2; j++)go[j][i] = go[go[j][i - 1]][i - 1];
}void getans(int x) {int len = a[x].l + m, cur = x, ans = 1;for (int i = log2(maxn); i >= 0; i--) {int pos = go[cur][i];if (pos && a[pos].r < len)ans += (1 << i), cur = pos;}res[a[x].idx] = ans + 1;
}int main() {fast;cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i].l >> a[i].r;a[i].idx = i;if (a[i].r < a[i].l)a[i].r += m;}sort (a + 1, a + n + 1);for (int i = 1; i <= n; i++) {a[i + n].idx = a[i].idx;a[i + n].l = a[i].l + m;a[i + n].r = a[i].r + m;}init();for (int i = 1; i <= n; i++)getans(i);for (int i = 1; i <= n; i++)cout << res[i] << ' ';return 0;
}