```
inline int getNextWarrior(int id){
int r;
warrior wa = w[id];
for (r=id; r<=2*n; r++){
if (w[r].l>wa.r) break;
}
return r-1;
}
inline void initJump(){
for (int i=1; i<=2*n; i++){
jump[i][0] = getNextWarrior(i);
}
}
```
这一段代码可以优化，你这样写复杂度高了，我修改了一下你的代码：
```
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
const int M = 1e9+5;
int n, m;
int k = 1;
struct warrior{
int id;
int l;
int r;
inline bool operator<(const warrior w) const{
return l < w.l;
}
inline bool operator>(const warrior w) const{
return l > w.l;
}
}w[N*2];
int jump[N*2][20];
inline int getNextWarrior(int id){
int r;
warrior wa = w[id];
for (r=k; r<=2*n; r++){
if (w[r].l>wa.r) break;
}
return r-1;
}
inline void initJump(){
for (int i=1; i<=2*n; i++){
jump[i][0] = getNextWarrior(i);
k = jump[i][0] + 1;
}
}
inline void calcJump(){
for (int i=1; (1<<i)<=n; i++){
for (int s=1; s<=2*n; s++){
jump[s][i] = jump[jump[s][i-1]][i-1];
}
}
}
int wr[N];
inline void calc(int n){
int dest = w[n].l + m;
int cur = n;
int ws=1;
for (int i=log2(N); i>=0; i--){
int pos = jump[cur][i];
if (pos && w[pos].r < dest){
ws += 1<<i;
cur = pos;
}
}
wr[w[n].id] = ++ws;
}
int main(){
scanf("%d %d", &n, &m);
for (int i=1; i<=n; i++){
w[i].id=i;
scanf("%d %d", &w[i].l, &w[i].r);
if (w[i].l > w[i].r){
w[i].r += m;
}
}
sort(w+1, w+n+1);
for (int i=1; i<=n; i++){
w[n+i].id=w[i].id;
w[n+i].l=w[i].l+m;
w[n+i].r=w[i].r+m;
}
initJump();
calcJump();
for (int i=1; i<=n; i++) calc(i);
for (int i=1; i<=n; i++) printf("%d ", wr[i]);
return 0;
}
```
by Mogullzr @ 2024-04-29 13:18:01
根据题目是可以知道这么一个结论的：我们将所有区间的左端点排序之后有端点会默认递增的，这样的话我们从左到右的每个区间所对应的最佳情况应该也是单调递增的，大概就是这么一个思路。
by Mogullzr @ 2024-04-29 13:21:24
@[Mogullzr](/user/1051776) 看懂了 意思就是每次findnext的时候都从上次找到的开始找 orz帮助很大
by akahoshi @ 2024-05-02 22:27:05