真是一个自闭的题目（调了一个上午+大半个下午）
从\(WA\)到\(WA+TLE\)到\(TLE\)到\(AC\)真的艰辛。
首先，这个题，我们可以考虑直接上四维KDTree来解决。
对于kdtree上的每个节点，我们维护三个值，分别表示各个维度的\(mn\)，当前节点的\(val\)（这个是用来每次更新\(ans\)的），子树的\(val\)的最大值（用来做估价函数）
首先\(build\)出整个kdtree
void up(int root){ for (int i=0;i<=3;i++) { if (t[root].l) t[root].mn[i]=min(t[root].mn[i],t[t[root].l].mn[i]); if (t[root].r) t[root].mn[i]=min(t[root].mn[i],t[t[root].r].mn[i]); } t[root].val=max(t[root].cao,max(t[t[root].l].val,t[t[root].r].val));}void build(int &x,int l,int r,int fa,int dd){ ymh = dd; int mid = l+r >> 1; dd++; if (dd==4) dd=0; x = mid; nth_element(t+l,t+x,t+r+1); t[x].fa=fa; t[x].cao=0; for (int i=0;i<=3;i++) t[x].mn[i]=t[x].d[i]; back[t[x].num]=x; if (l 然后，我们用kdtree来维护一个做lis的过程
其中，我们先对所有点进行排序，然后依次枚举他们。
对于一次\(query\)，我们首先\(check\)一下当前点能不能更新\(ans\)，然后通过子树max来估价，判断先进入哪个子树，或者进不进入当前子树
bool get(KD a,KD b){ for (int i=0;i<=3;i++) if (a.d[i]>b.d[i]) return 0; return 1;}int calc(int x,KD b){ if (!x) return 0; for (int i=0;i<=3;i++) if (t[x].mn[i]>b.d[i]) return 0; return 1;}void query(int x,KD caonima,int dd){ if (!x) return ; // cout< <<" "< <<" "< <<" "< <<" "< < =t[t[x].r].val) { if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4); if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4); } else { if (d2 && t[t[x].r].val>tmp) query(t[x].r,caonima,(dd+1)%4); if (d1 && t[t[x].l].val>tmp) query(t[x].l,caonima,(dd+1)%4); }} 下面是这个题的重点
就是因为\(lis\)，所以我们要修改当前点的\(val\)以及他子树内的\(val\)，为了下一个点的统计。这里我们修改的方式是找到这个点对应的kdtree上的节点，然后不停的暴力向上跳。
我们首先把这个对应节点的\(val\)弄成这次我们\(query\)的答案+1，然后依次修改祖先们的子树\(max\)
void upp(int x){ //t[x].val=max(t[x].val,t[x].cao); t[x].val=max(t[x].cao,max(t[t[x].l].val,t[t[x].r].val));}void update(int x,int pp){ t[x].cao=pp; upp(x); x=t[x].fa; while (x) { //cout<<"****"< <<" "< <<" "< <<" "< < 那么其实这个题就应该差不多了
不得不说细节真的是很多的qwq
具体还是看代码吧
kdtree真神奇！
// luogu-judger-enable-o2// luogu-judger-enable-o2#include#include #include #include #include #include #include