[CH弱省胡策R2]TATT

题目描述

四维空间真是美妙。现在有n个四维空间中的点，请求出一条最长的路径，满足任意一维坐标都是单调不降的。 注意路径起点是任意选择的，并且路径与输入顺序无关（路径顺序不一定要满足在输入中是升序）。

路径的长度是经过的点的数量，任意点只能经过一次。

输入输出格式

输入格式：

第一行一个整数n。 接下来n行，每行四个整数ai,bi,ci,di。表示四维坐标

输出格式：

一行一个整数，表示最长路径的长度

输入输出样例

输入样例#1：

4 2 3 33 2333 2 3 33 2333 2 3 33 2333 2 3 33 2333

输出样例#1：

4

说明

测试点编号 n m 特殊说明

1 n≤2000 m≤109 2 n≤ 5∗104 m≤8 3−4 同上 m≤105 所有点的第三，四维坐标相同 5−6 同上 同上 所有点的第四维坐标相同 7−8 同上 m≤100 无 9−10 同上 m≤109

---

所以咱就被这题坑了一晚上…… 虽然感觉学到了很多但是咱还是要说:

(╯‵□′)╯︵┻━┻

所以看咱的程序时可能会出现一些莫名其妙的变量、调试信息之类的不要在意~ 另外，这题明明是R1的A题啊……

---

思路: 这次就讲讲咱的思路过程吧。 首先。这显然是K-D树。 然后，这是个DP，四维的最长不下降子序列。

好，于是有了咱的第一个版本的代码: 版本一 然后发现又T又WA…… 很显然，这个版本的剪枝太naive了，而且逻辑还有问题，以至于不仅效率和暴力差不多还会WA……. 本身K-D树就是靠剪枝混饭吃的……

那么我们获得了版本二: 版本二 然后又T成了ZZ…… 显然这个版本的剪枝并不见得比上个版本高明了多少(事实上有些情况更慢了)，但至少能保证正确率……

于是来到版本三: 版本三 然后事实上这个版本的剪枝和上一个版本已经有了巨大差别，尤其是query部分已经足够快了。 但是，modify操作的调用次数迷之巨大…… 所以，依然T成ZZ……

然后我们得到了最终版本一:

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=50009; int main_d; inline int minn(int a,int b){if(a<b)return a;return b;} inline int maxx(int a,int b){if(a>b)return a;return b;} inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();} return x*f; } struct point { int coord[4],mn[4],id,l,r,mv,v,f; int &operator [](int x) { return coord[x]; } void init() { for(int i=0;i<=3;i++) mn[i]=coord[i]; v=mv=f=0; } }; bool operator <(point satori,point koishi) { return satori[main_d]<koishi[main_d]; } inline bool ecmp(point a,point b) { for(int i=0;i<=3;i++) if(a[i]!=b[i]) return 0; return 1; } inline bool judge(point satori,point koishi) { for(int i=0;i<=3;i++) if(satori[i]>koishi[i]) return 0; return 1; } inline bool valid(point satori,point koishi) { for(int i=0;i<=3;i++) if(satori.mn[i]>koishi[i]) return 0; return 1; } int p[N]; int sumt[5]; struct k_dimensional_tree { int root,maxval; point t[N]; void update(int x) { for(int i=0;i<=3;i++) t[x].mn[i]=minn(t[x].mn[i],minn(t[t[x].l].mn[i],t[t[x].r].mn[i])); t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv)); } void push(int x) { t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv)); } inline int check(int x,point p) { if(!x)return x; int ret=1; for(int i=0;i<=3;i++) if(p[i]<t[x].mn[i]) ret=0; return ret; } int biu(int l,int r,int d) { main_d=d; int mid=l+r>>1,nxt; nth_element(t+l,t+mid,t+r+1); nxt=d+1; if(nxt==4) nxt=1; t[mid].init(); if(l<mid) t[mid].l=biu(l,mid-1,nxt),t[t[mid].l].f=mid; if(mid<r) t[mid].r=biu(mid+1,r,nxt),t[t[mid].r].f=mid; update(mid); return mid; } void query(int x,point p,int d) { sumt[0]++; //printf("now in %d\n",x); if(judge(t[x],p) && maxval<t[x].v) maxval=t[x].v; int nxt=d+1; if(nxt==4) nxt=1; if(p[d]>=t[x][d]) { int a=t[x].l,b=t[x].r; if(t[a].mv<t[b].mv) swap(a,b); if(valid(t[a],p) && t[a].mv>maxval) query(a,p,nxt); if(valid(t[b],p) && t[b].mv>maxval) query(b,p,nxt); } else if(valid(t[t[x].l],p) && t[t[x].l].mv>maxval) query(t[x].l,p,nxt); } void modify(int x,int v) { t[x].v=v; push(x); while(x=t[x].f) push(x); } }koishi; bool pcmp(int a,int b) { for(int i=0;i<=3;i++) if(koishi.t[a][i]!=koishi.t[b][i]) return koishi.t[a][i]<koishi.t[b][i]; return 0; } int main() { int n=read(); for(int i=1;i<=n;i++) { p[i]=i; for(int j=0;j<=3;j++) koishi.t[i][j]=read(); koishi.t[i].id=i; } koishi.root=koishi.biu(1,n,1); sort(p+1,p+n+1,pcmp); for(int i=1;i<=n;i++) { koishi.maxval=0; int o=p[i]; //printf("querying %d:%d %d %d %d\n",p[i],koishi.t[o][0],koishi.t[o][1],koishi.t[o][2],koishi.t[o][3]); koishi.query(koishi.root,koishi.t[p[i]],1); koishi.modify(p[i],koishi.maxval+1); //cerr<<(double)clock()/CLOCKS_PER_SEC<<endl; } printf("%d\n",koishi.t[koishi.root].mv); //cerr<<"my"<<sumt[0]<<endl; return 0; }

对于随机数据modify操作的次数是之前的二十分之一……

好事实上我们已经完美解决了这题但是……不觉得前两个版本T得很玄学吗?

于是咱又得到了最终版本2:

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=50009; int main_d; inline int minn(int a,int b){if(a<b)return a;return b;} inline int maxx(int a,int b){if(a>b)return a;return b;} inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();} return x*f; } struct point { int coord[4],mn[4],mx[4],l,r,mv,v,ll,rr; int &operator [](int x) { return coord[x]; } void init() { for(int i=0;i<=3;i++) mn[i]=mx[i]=coord[i]; v=mv=0; } }; bool operator <(point satori,point koishi) { return satori[main_d]<koishi[main_d]; } inline bool ecmp(point a,point b) { for(int i=0;i<=3;i++) if(a[i]!=b[i]) return 0; return 1; } inline bool valid(point satori,point koishi) { for(int i=1;i<=3;i++) if(satori.mn[i]>koishi[i]) return 0; return 1; } inline bool judge(point satori,point koishi) { for(int i=0;i<=3;i++) if(satori[i]>koishi[i]) return 0; return 1; } int p[N]; struct k_dimensional_tree { int root,maxval; point t[N]; void update(int x) { for(int i=0;i<=3;i++) { t[x].mn[i]=minn(t[x].mn[i],minn(t[t[x].l].mn[i],t[t[x].r].mn[i])); t[x].mx[i]=maxx(t[x].mx[i],maxx(t[t[x].l].mx[i],t[t[x].r].mx[i])); } t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv)); } void push(int x) { t[x].mv=maxx(t[x].v,maxx(t[t[x].l].mv,t[t[x].r].mv)); } int biu(int l,int r,int d) { main_d=d; int mid=l+r>>1,nxt; nth_element(t+l,t+mid,t+r+1); nxt=d+1; if(nxt>3) nxt=1; t[mid].init(); t[mid].ll=l; t[mid].rr=r; if(l<mid) t[mid].l=biu(l,mid-1,nxt); if(mid<r) t[mid].r=biu(mid+1,r,nxt); update(mid); return mid; } void query(int x,point p,int d) { if(judge(t[x],p) && maxval<t[x].v) maxval=t[x].v; int nxt=d+1; if(nxt==4) nxt=1; if(p[d]>=t[x][d]) { int a=t[x].l,b=t[x].r; if(t[a].mv<t[b].mv) swap(a,b); if(valid(t[a],p) && t[a].mv>maxval) query(a,p,nxt); if(valid(t[b],p) && t[b].mv>maxval) query(b,p,nxt); } else if(valid(t[t[x].l],p) && t[t[x].l].mv>maxval) query(t[x].l,p,nxt); } inline bool in(point satori,point koishi) { for(int i=0;i<4;i++) if(koishi[i]<satori.mn[i] || satori.mx[i]<koishi[i]) return 0; return 1; } bool inr(int satori,int koishi) { if(t[satori].ll<=koishi && koishi<=t[satori].rr) return 1; return 0; } void modify(int x,int p,int v) { if(x==p) { t[x].v=v; push(x); return; } if(t[x].l && inr(x,p) && in(t[x],t[p])) modify(t[x].l,p,v); if(t[x].r && inr(x,p) && in(t[x],t[p])) modify(t[x].r,p,v); push(x); } }koishi; bool pcmp(int a,int b) { for(int i=0;i<=3;i++) if(koishi.t[a][i]!=koishi.t[b][i]) return koishi.t[a][i]<koishi.t[b][i]; return 0; } int main() { int n=read(); for(int i=1;i<=n;i++) { p[i]=i; for(int j=0;j<=3;j++) koishi.t[i][j]=read(); } koishi.root=koishi.biu(1,n,1); sort(p+1,p+n+1,pcmp); for(int i=1;i<=n;i++) { koishi.maxval=0; koishi.query(koishi.root,koishi.t[p[i]],1); koishi.modify(koishi.root,p[i],koishi.maxval+1); } printf("%d\n",koishi.t[koishi.root].mv); return 0; }

虽然没有上一个版本优(各种意义上)，但是能稳过~

可以看到咱只是在modify函数里加了一个判断目标节点编号是否在当前节点区间内就过掉了~ 为什么呢? 因为，在前几个版本里，如果出现了目标点与当前查询节点共线的情况，就会同时递归左儿子和右儿子(因为目标节点同时处于左儿子和右儿子所表示的区间内)，只要被这么卡上哪怕一次都是很疼的……

不过只是被卡几次的话还是很稳的。 但是，不要忘了这题有4维，任一维共线都会出事，而且虽然根据样例的坐标范围共线的概率还不算大(0~10000的范围几乎无影响)，但如果坐标范围很小的话，比如咱造数据时开的0~10……比!暴!力!还!慢!很!多!!!

所以卡一卡这样的情况就可以过了~

---

另外有个小插曲:标程，采用了一个个插入+替罪羊树重构。洛谷上82分T了…… 原因很显然是跟咱的程序一样的……要不是靠替罪羊续秒咱还真不知道标程君怎么A的…… 换句话说……如果替罪羊能给咱的程序也续上一秒的话…… 神奇的标程君