不只是 P3369 题解

· · 算法·理论

1.前言

第一次文章长度超过 10k！

这是对我所有学习过的类平衡树模板题的解决方法。位置越靠后方法越优。

对于以前写过的文章的扩展。

推荐阅读顺序：6\to4\to7\to8\to11\to9\to10。

上面没有的就是不推荐阅读。

会给出 10 和 11 的代码。

# 2.暴力 考虑最朴素的方式——对数列开个桶，记录每一个元素是否存在，插删就是 $O(1)$ 的，前驱后继查询直接遍历枚举，得到一个 $O(n^2)$ 的复杂度。 # 3.vector 考虑使用以上同样的方式，用 vector 维护同样操作。 使用二分+insert，虽然 insert 是 $O(n)$ 的但是时间常数极小，可以过掉 P3369！ 然而还是不如以下的方法。 # 4.分块 以前直接说和 0-1 trie 一样一笔带过了，但是后来发现很不对。 对值域分块，以查询前驱为例。 先找查询元素所在块里，查询元素之前有没有元素，如果有就做完了。 否则从查询元素所在块开始向前枚举块，直到块内有元素，然后找到块内元素的最大值。然后就做完了。 # 5.pb_ds tree（红黑树） 考虑用 pb_ds 中的 tree 维护。 ```cpp #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; __gnu_pbds::tree<Key,Mapped,Cmp_Fn=std::less<Key>,Tag=rb_tree_tag,Node_Update=null_tree_node_update,Allocator=std::allocator<char>> ``` 声明： ```cpp __gnu_pbds::tree<std::pair<int,int>,__gnu_pbds::null_type,std::less<std::pair<int, int>>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>trr; ``` 比较长，但是用法和 vector 几乎相似，但是是单 log 的！ 这里应该讲讲手写平衡树，但是 pbds 很快，所以就不讲了。 # 6.值域线段树 对应原文章的 0-1 trie，发现原先写的东西完全错误，就来补一补。 对原序列建立值域线段树，子树内有存在就是 $1$，否则就是 $0$。 以下以前驱为例。 找到查询元素所对应的结点，一直向上走直到走到满足如下条件： 1. 上一个经过的结点是这个结点的右儿子； 2. 左儿子是 $1$。 然后在这个节点左儿子上开始走，走到最右边的 $1$。然后得出答案。 # 7.压位 trie 请保证你看懂了 $6$。 考虑把 trie 扩展，变成四进制的 0-1-2-3 trie 或者八进制的 0-1-2-3-4-5-6-7 trie。一般习惯使用 $64$ 进制，复杂度能除个常数。 # 8.proto-vEB 请保证你看懂了 $4$ 和 $7$。 我们可以将值域补全为 $2^{2^k}$ 形式，那么不仅 $\sqrt{n}$ 是整数，$\sqrt{\sqrt{n}}$，$\sqrt{\sqrt{\sqrt{n}}}$，$\sqrt{\sqrt{\sqrt{\sqrt{n}}}}$ 等也是整数。 先别急着说补全的时候可能把值域改成平方级别（如 $n=65537$ 时）所以预处理承受不了，先看看后面的。 那么我们可以借鉴 Sqrt Tree 的思想，在分块里头，再套上分块！ 注意不仅要对每个块内的信息维护一个小一点的 vEB（我们之后把这个东西称作“簇”），还要开一个小 vEB 代表每个元素里面有没有东西（我们之后把这个东西称作“汇总”）。 分析复杂度，判断存在是 $O(\log \log n)$，没问题，增删最大最小的话，——怎么是 $O(\log n)$？那和平衡树或 0-1 trie 有什么区别？ 别急，先看看为什么是 $\log$ 而不是 $\log \log$。 考虑增删的时候，不仅要增删对应簇，还要增删汇总。所以需要调用两次递归。所以就是 $O(\log n)$（证明不用在这里说了吧，主定理乱杀），最大最小同理。 查询前驱后继反而更慢，因为不仅要调用两次递归（可能是这个簇中的最大，但后缀在下个簇的最小值），还需要调用一次最小函数，时间复杂度为 $O(\log n\log \log n)$。 # 9.x-fast trie 请保证你看懂了 $6$。 同样是维护一个 0-1 trie，但是首先预处理出来每个节点的最大值和最小值。 向上跳的过程用二分解决，向下的过程可以通过上面维护的东西 $O(1)$ 做就行。 但是你其实注意到那个"从右儿子进入"是没有可二分性的，我们只能二分出来另外一个儿子是 $1$。 这就导致了我们求的是前驱和后继中的一个而不是特定给的求前驱和后继。 目前做法就是对于所有插入的数维护一个链表，然后额外用一个哈希表维护每一个结点对应的定位，然后求的时候看看是前驱还是后继，如果不对的话就对结果进行微调。 # 10.y-fast trie 请保证你看懂了 $4$、$5$ 和 $9$。 以 $\log$ 分块。 对于块内使用 $5$ 的方法解决。 对于每一个块出个代表元素，这个代表元素不一定要在块中，但一定要满足比下一块的最小值和下一块的代表元素小且比上一块的最大值和上一块的代表元素大，然后把这些代表元素拿出来跑 $10$。 以前驱为例，如果跑出来的块最小值比查询值还要大，说明查到了后缀，所以要把查到的块变成上一个块。然后在块里二分就可以。 这是没有插删的情况。 有插删的话，考虑如果大小是原先的两倍就分裂开，是原先的一半就和下一个块合并。如果大小又大的再分裂开。 复杂度里的 $\log$ 会被直接摊掉，所以也是 $\log\log$ 的（复杂度分析和 Four Russian 类似）。 ## 查询前驱块和后继块中的一个 不做说明，过程和 $10$ 的差不多。 ```cpp int getblk(int w) { int l=1,r=25,mid,ans=1; while(l<=r) { int mid=l+r>>1,val=(v&(((1<<mid)-1)<<(25-mid)))>>(25-mid); if(hs.find((1<<mid)+val-1)!=hs.end()){ans=hs[(1<<mid)+val-1];l=mid+1;} else r=mid-1; } if(ytr[ans].ls==0&&ytr[ans].rs==0)return ytr[ans].x; if(ytr[ans].ls==0)return ytr[ytr[ans].rs].mn; return nxt[ytr[ytr[ans].ls].mx]; } ``` ## 插入删除 直接找对应块插入或删除，对块进行必要的分裂或合并处理。 ### 内层插入删除 ```cpp int insert(int &u,int v,int id,int dep) { int res; if(!u)u=++idx2; if(dep==-1) { ytr[u].mn=ytr[u].mx=ytr[u].x=++idx1; w[idx]=v;res=u; } else { if(v&(1<<dep))res=insert(yrt[u].ls,v,id<<1|1,dep-1); else res=insert(yrt[u].rs,v,id<<1,dep-1); pushup(u); } hs[(1<<24-dep)+id-1]=u; return res; } int del(int &u,int v,int id,int dep) { int res; if(!u)u=++idx2; if(dep==-1){res=ytr[u].x;u=0;} else { if(v&(1<<dep))res=del(yrt[u].ls,v,id<<1|1,dep-1); else res=del(yrt[u].rs,v,id<<1,dep-1); pushup(u); } if(!u)hs.erase((1<<24-dep)+id-1); return res; } ``` pushup 用于维护最大值及最小值，大家应该都会。 ### 平衡树合并 tree 有个特别牛的东西叫做 merge，可以直接合并。 这里代码很短，而且用的次数只有 2 次，直接放到外层删除里不作为函数了。 ### 平衡树分裂 tree 有个特别牛的东西叫做 split，可以直接分裂。 用了 3 次还比较长，放个函数。 ```cpp void split(int u) { tr[u].split(*tr[u].find_by_order(tr[u].size()/2-1),tr[idx1+1]); swap(tr[idx1+1],tr[u]); int y=insert(rt,*tr[idx1+1].rbegin(),0,24),z=pre[x]; nxt[z]=y;nxt[y]=x;pre[x]=y;pre[y]=z; } ``` ### 外层插入 ```cpp void Insert(int w) { int x=getblk(w); tr[x].insert(w); if(clu[x].size()>50)split(x); } ``` ### 外层删除 和插入不同，合并的时候需要判断是合并左块还是右块。 虽然理论上来说可以随便找一个合并，但是你不能保证你选择的一定存在。 ```cpp void Del(int v) { int x=getblk(v); tr[x].erase(tr[x].find(v)); if(clu[x].size()<12) { int a=pre[x],b=nxt[x],y=pre[a]; if(a==0&&b==0) { if(tr[x].size()==0&&x!=1)del(rt,w[x],0,24); return; } if(a) { tr[x].join(tr[a]); del(rt,w[a],0,24); nxt[y]=x;pre[x]=y; if(tr[x].size()>50)split(x); } else { tr[b].join(tr[x]); del(rt,w[x],0,24); pre[b]=a;nxt[a]=b; if(tr[b].size()>50)split(b); } } } ``` ## 最大值/前驱/最小值/后继/判断元素是否存在 最大值为 $+\infty$ 的前驱，最小值为 $-\infty$ 的后继。判断元素是否存在就是看前驱/后继等不等于自己，所以就只说前驱/后继了。 先跑 x-fast trie 找到前驱/后继块，然后找到块中最大值/最小值。如果找到了正好在里面的块就用上平衡树查找。 ```cpp int pred(int w) { int x=getblk(w); if(tr[x].empty()||*tr[x].begin()>w) { if(!pre[x])return NIL; return *tr[pre[x]].rbegin(); } return *(clu[x].upper_bound(w)-1); } int succ(int w) { if(ytr[1].ls==0&&ytr[1].rs==0)return NIL; int x=getblk(w); if(tr[x].empty()||*tr[x].rbegin()<w) { if(!nxt[x])return NIL; return *tr[nxt[x]].begin(); } return *tr[x].lower_bound(w); } ``` # 11.vEB 请保证你看懂了 $8$。 真正的 vEB 树是这样维护的，我们不仅要记录大小、汇总和每个簇，还要记录最大值和最小值。**并且最小值中维护的元素不会出现在任意一个簇中。** 首先我们先把第一个坑填上：预处理时会做到 $n^2$。 考虑我们先不要求值域为 $2^{2^k}$，先把他补全为 $2^k$。 定义 $\sqrt[\uparrow]{2^k}=2^{\lfloor\frac{k}{2}\rfloor},\sqrt[\downarrow]{2^k}=2^{\lceil \frac{k}{2}\rceil}$。 那么我们的汇总的大小变成了大小为 $\sqrt[\uparrow]{n}$ 的 vEB 树，每个簇的大小都变成了 $\sqrt[\downarrow]{n}$。 接下来是操作讲解。 最大最小值直接 $O(1)$ 查根节点就行了。 ## 初始定义 ```cpp struct node{int sz,mn,mx,smr;vector<int>ch;}vEB[N]; int dnsq(int u){return 1<<(lg[vEB[u].sz]>>1);} int upsq(int u){return 1<<(lg[vEB[u].sz]+1>>1);} int clus(int u,int x){return x/dnsq(u);} int dnid(int u,int x){return x%dnsq(u);} int upid(int u,int x,int y){return x*dnsq(u)+y;} ``` ## 建树及判断元素是否存在 和 proto-vEB 几乎一样的部分。 ```cpp int build(int u,int sz) { vEB[u].sz=sz; vEB[u].mn=vEB[u].mx=-1; if(sz==2)return u; vEB[u].smr=build(++idx,upsq(u)); for(int i=0;i<sz;i++)vEB[u].ch.push_back(build(++idx,dnsq(u))); return u; } bool find(int u,int x) { if(vEB[u].mn==x||vEB[u].mx==x)return 1; if(vEB[u].sz==2)return 0; return find(vEB[u].ch[clus(u,x)],dnid(u,x)); } ``` ## 查询元素后继和前驱 ```cpp int succ(int u,int x) { if(vEB[u].sz==2) { if(x==0&&vEB[u].mx==1)return 1; return NIL; } if(vEB[u].mn!=NIL&&x<vEB[u].mn)return vEB[u].mn; int tmp=vEB[vEB[u].ch[clus(u,x)]].mx; if(tmp!=NIL&&dnid(p,x)<tmp)return upid(u,clus(u,x),succ(vEB[u].ch[clus(u,x)],dnid(p,x))); int nxc=succ(vEB[u].smr,clus(u,x)); if(nxc==NIL)return NIL; return upid(u,nxc,vEB[vEB[u].ch[nxc]].mn); } int pred(int u,int x) { if(vEB[u].sz==2) { if(x==1&&vEB[u].mx==0)return 0; return NIL; } if(vEB[u].mx!=NIL&&x>vEB[u].mx)return vEB[u].mx; int tmp=vEB[vEB[u].ch[clus(u,x)]].mn; if(tmp!=NIL&&dnid(p,x)>tmp)return upid(u,clus(u,x),pred(vEB[u].ch[clus(u,x)],dnid(p,x))); int prc=pred(vEB[u].smr,clus(u,x)); if(prc==NIL) { if(vEB[u].mn!=NIL&&x>vEB[u].mn)return vEB[u].mn return NIL; } return upid(u,prc,vEB[vEB[u].ch[prc]].mn); } ``` 后继就是先找在自己这个簇的后缀，如果没有就找这个簇在汇总中的后缀，都没有就是 NIL。 前驱基本对称，大家可以找找不同。 不同之处在于注意最小值是不存在后面的簇里的，所以需要判掉。 ## 插入元素 ```cpp void insert(int u,int x) { if(vEB[u].mn==NIL) { vEB[u].mn=vEB[u].mx=x; return; } if(x<vEB[u].mn)swap(x,vEB[u].mn); if(vEB[u].sz>2) { int tmp=vEB[u].ch[clus(u,x)]; if(vEB[tmp].mn==NIL) { insert(vEB[u].smr,clus(u,x)); vEB[tmp].mn=vEB[tmp].mx=dnid(u,x); } else insert(tmp,dnid(u,x)); } vEB[u].mx=max(vEB[u].mx,x); } ``` 传统的两次递归显然是不能满足我们的复杂度了。 这时候我们要记一个神秘的不下传的最小值的原因就要体现出来了，如果簇为空，可以 $O(1)$ 放到最小值里，然后再把簇插入到汇总里，否则的话汇总就不用动，把元素插入到簇里即可。 ## 删除元素 ```cpp void del(int u,int x) { if(vEB[u].mn==vEB[u].mx) { vEB[u].mn=vEB[u].mx=NIL; return; } if(vEB[u].sz==2) { vEB[u].mn=vEB[u].mx=!x; return; } if(x==vEB[u].mn)vEB[u].mn=x=upid(u,vEB[vEB[u].smr].mn,vEB[vEB[u].ch[vEB[vEB[u].smr].mn]].mn); del(vEB[u].ch[clus(u,x)],dnid(u,x)); if(vEB[vEB[u].ch[clus(u,x)]].mn==NIL) { del(vEB[u].smr,clus(u,x)); if(x==vEB[u].mx) { if(vEB[vEB[u].smr].mx==NIL)vEB[u].mx=vEB[u].mn; else vEB[u].mx=upid(u,vEB[vEB[u].smr].mx,vEB[vEB[u].ch[vEB[vEB[u].smr].mx]].mx); } } else if(x==vEB[u].mx)vEB[u].mx=upid(u,clus(u,x),vEB[vEB[u].ch[clus(u,x)]].mx); } ``` 最难的一个操作。 注意这个函数需要保证删除元素存在。 如果只有一个元素就直接删，大小为 $2$ 就删一个。 如果删除的是最小值就把最小值改成次小值，然后删除次小值，删除的是最大值同理。 然后往下删除，如果为空就删汇总。 注意到如果删了汇总的话删簇的时候一定是 $O(1)$ 的，所以复杂度是正确的。 文章结束了，后面好像只能静态，动态需要用到我不会的技巧，所以后面基本上是写给自己看的了，也最好不要往后看，可能会有一些知识性漏洞。 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- 你确定要往后看吗？这是最后一次警告！ ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- # $\omega$.? 口胡。 我们能不能把 y-fast trie 再度分块，分块很多次啊，块间 x-fast trie 块内下一层，最后的最后平衡树，这样是 $O(n\log^*n)$ 的？ # $\omega_1^{CK}$.??? 我们能不能块间用的不是 x-fast trie，用的是下一个数据结构，一直分，直到最后一层才用 x-fast trie，这样是 $O(n\alpha(n))$ 的？ --- 所以这样看来的话（静态）平衡树问题和区间 RMQ 差不多？ y-fast trie 对应 Four Russian，vEB 对应 Sqrt Tree？ 那么是不是说可能会有线性的做法？期待一下学术界。 参考文献： 1. [你所不了解的数据结构-van Emde Boas 树](https://www.cnblogs.com/RuntimeErr/p/16599941.html)； 2. [y-fast trie 简介](https://www.luogu.com/article/o99sh6m1)； 3. [y-fast trie](https://www.luogu.com/article/40yu68f8)。