题目概述

有 $n$ 个基地，每个基地可以发射和接收 $[x_i,y_i]$ 频率内的信号，坐标为 $l_i$ ，且 $i$ 号基地只能往前发射到距离不超过 $L$ 的基地。求 $[2,n]$ 的基地发射信号到 $1$ 号基地需要经过的最少基地数。

解题报告

暴力DP：$f_{i}=max\{f_j|j<i,l_i-l_j\le L,[x_j,y_j]\cap[x_i,y_i]\not=\emptyset\}+1​$ 。

两个线段有交集其实就是 $x_i\le y_j,x_j\le y_i$ ，我们可以用KDT来做这个东西。那么维护 $i$ 号基地能够到达的基地的KDT，每次找最大值的时候就在KDT上暴力查询一下就行了。复杂度可能是 $O(n\sqrt n)$ ？

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=250000;

int n,lim,X[maxn+5],lx[maxn+5],rx[maxn+5],ID[maxn+5],ans;
int D,ro,son[maxn+5][2],fa[maxn+5],MN[maxn+5][2],MX[maxn+5][2],MIN[maxn+5];
struct Point{
    int x[2],v;inline Point(int X=0,int Y=0,int V=0) {x[0]=X;x[1]=Y;v=V;}
    inline bool operator < (const Point &a) const {return x[D]<a.x[D];}
}a[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Pushup(int p){
    for (int i=0;i<2;i++) MN[p][i]=MX[p][i]=a[p].x[i];
    MIN[p]=min(a[p].v,min(MIN[son[p][0]],MIN[son[p][1]]));
    for (int j=0;j<2;j++)
        for (int i=0;son[p][j]&&i<2;i++)
            MN[p][i]=min(MN[p][i],MN[son[p][j]][i]),MX[p][i]=max(MX[p][i],MX[son[p][j]][i]);
}
inline bool cmp(const int &p,const int &q) {return a[p]<a[q];}
int Build(int L,int R,int d=0,int pre=0){
    int m=L+(R-L>>1);D=d;nth_element(ID+L,ID+m,ID+R+1,cmp);int p=ID[m];son[p][0]=son[p][1]=0;fa[p]=pre;
    if (L<m) son[p][0]=Build(L,m-1,d^1,p);if (m<R) son[p][1]=Build(m+1,R,d^1,p);Pushup(p);return p;
}
inline void Update(int p,int k) {a[p].v=k;for (int i=p;i;i=fa[i]) Pushup(i);}
void Ask(int p,int x,int y){
    if (!p||x>MX[p][1]||MN[p][0]>y||MIN[p]>=ans) return;
    if (x<=MN[p][1]&&MX[p][0]<=y) {ans=min(ans,MIN[p]);return;}
    if (x<=a[p].x[1]&&a[p].x[0]<=y) ans=min(ans,a[p].v);
    for (int d=MIN[son[p][0]]>MIN[son[p][1]],i=0;i<2;d^=1,i++) Ask(son[p][d],x,y);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(lim);for (int i=2;i<=n;i++) readi(lx[i]),readi(rx[i]),readi(X[i]);
    MIN[0]=2e9;a[1]=Point(-2e9,2e9,0);ID[1]=1;
    for (int i=2;i<=n;i++) ID[i]=i,a[i]=Point(lx[i],rx[i],2e9);ro=Build(1,n);
    for (int i=2,j=1;i<=n;i++){
        while (X[i]-X[j]>lim) Update(j++,2e9);ans=2e9;Ask(ro,lx[i],rx[i]);
        ans<2e9?ans++:ans=-1;printf("%d\n",ans);if (~ans) Update(i,ans);
    }return 0;
}