题目概述

CF1427C

解题报告

我又被傻子题干翻了😭，首先 $O(n^2)$ DP非常好想，需要优化。

由于保证了 $t_i<t_{i+1}$ ，所以当 $j+2(r-1)\le i$ 时，$j$ 一定能到 $i$ 。

所以每次至多需要检查 $2(r-1)$ 个位置，在 $i-2(r-1)$ 之前的位置只需要记录一下前缀最大值就行了。

或者你可以像我一样写KDT，莫名其妙也能过。

示例程序

#include<cstdio>
using namespace std;
const int maxn=100000;

int r,n,T[maxn+5],X[maxn+5],Y[maxn+5],f[maxn+5],MAX[maxn+5],ans;

inline int abs(int x) {return x<0?-x:x;}
int main(){
    scanf("%d%d",&r,&n);for (int i=1;i<=n;i++) scanf("%d%d%d",&T[i],&X[i],&Y[i]);
    for (int i=1,j;i<=n;i++){
        if (X[i]-1+Y[i]-1<=T[i]) f[i]=1;
        for (j=i-1;j && T[j]+(r-1<<1)>T[i];j--)
            if (T[j]+abs(X[i]-X[j])+abs(Y[i]-Y[j])<=T[i])
                if (f[j] && f[j]+1>f[i]) f[i]=f[j]+1;
        if (MAX[j] && MAX[j]+1>f[i]) f[i]=MAX[j]+1;
        if (f[i]>ans) ans=f[i];
        MAX[i]=MAX[i-1]>f[i]?MAX[i-1]:f[i];
    }
    printf("%d\n",ans);return 0;
}

示例程序-KDT

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
const int maxn=200000;

int n,m,D,ro,son[maxn+5][2],MN[maxn+5][2],MX[maxn+5][2],MT[maxn+5],MF[maxn+5],ans;
struct Point {int id,t,f,x[2];inline bool operator < (const Point &a) const {return x[D]<a.x[D];}} a[maxn+5];
int T[maxn+5],ID[maxn+5],fa[maxn+5];pair<int,int> P[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];
    MT[p]=a[p].t;MF[p]=a[p].f;
    for (int j=0;j<2;j++) if (son[p][j]) MT[p]=min(MT[p],MT[son[p][j]]);
    for (int j=0;j<2;j++) if (son[p][j]) MF[p]=max(MF[p],MF[son[p][j]]);
    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]);
}
int Build(int L,int R,int d=0){
    int m=L+(R-L>>1);D=d;nth_element(a+L,a+m,a+R+1);son[m][0]=son[m][1]=0;
    if (L<m) son[m][0]=Build(L,m-1,d^1);if (m<R) son[m][1]=Build(m+1,R,d^1);Pushup(m);
    if (son[m][0]) fa[son[m][0]]=m;if (son[m][1]) fa[son[m][1]]=m;return m;
}
void Update(int p) {for (int x=p;x;x=fa[x]) Pushup(x);}
#define mindis(p,x,y) (MT[p]+max(MN[p][0]-(x),0)+max((x)-MX[p][0],0)+max(MN[p][1]-(y),0)+max((y)-MX[p][1],0))
inline int absi(int x) {return x<0?-x:x;}
void Ask(int p,int x,int y,int t){
    if (!p) return;if (MF[p]<=ans) return;if (mindis(p,x,y)>t) return;
    if (a[p].t+absi(a[p].x[0]-x)+absi(a[p].x[1]-y)<=t) ans=max(ans,a[p].f);
    int d=MF[son[p][0]]<MF[son[p][1]];
    Ask(son[p][d],x,y,t);d^=1;Ask(son[p][d],x,y,t);
}
int main(){
    freopen("C.in","r",stdin);freopen("C.out","w",stdout);
    readi(m);readi(n);
    for (int i=1;i<=n;i++) readi(T[i]),readi(P[i].fr),readi(P[i].sc);
    for (int i=1;i<=n;i++) a[i].t=1e9,a[i].x[0]=P[i].fr,a[i].x[1]=P[i].sc,a[i].id=i;
    ro=Build(1,n);int F=0;
    for (int i=1;i<=n;i++) ID[a[i].id]=i;
    for (int i=1;i<=n;i++){
        ans=0;Ask(ro,P[i].fr,P[i].sc,T[i]);
        if (ans) ans++;
        if (!ans && P[i].fr-1+P[i].sc-1<=T[i]) ans=1;
        if (ans){
            int now=ID[i];
            a[now].t=T[i];a[now].f=ans;Update(now);
        }
        if (ans>F) F=ans;
    }
    printf("%d\n",F);
    return 0;
}