闲话：Luogu总共105篇题解中只有4篇01Tire树解法，虽说是非正解但未免也太少了些（貌似也不少？）……总之01Tire树的效率并不低，这道题用01Tire是很轻松的。
Q：这题为什么可以用01Tire树解？
能否解决一个问题，无非于三个点：可行性，空间，时间。
本题要求维护一个有序数集，能进行元素修改和查询。
而01Tire树通过数字的二进制01串储存，根据这条特性，01Tire树就可以作为维护有序数集的天然容器。
可行性上，01Tire树可解，至于空间和时间，等到代码部分结束后再讨论。
话不多说，接下来就进入01tire树解法详解
首先看到数据范围 \(|x| \le 10^7\) ,意识到数据中可能有负数，然而01Tire只能维护非零整数，于是使用最简单粗暴的方法：给所有数字加上 1e7 ，在输出时再减去即可。
这样数据范围就变成了 $ x \le 2 * 10^7 $ ，实际上根据01Tire建树的方法，这样只会增加一层，因此不用担心时空爆炸。
由于01Tire树所需空间比较大，因此我习惯于提前预估一下01Tire的深度，编译 log2(2e7) = 24.2 于是取 25 作为01Tire的深度。
至此，我们可以写出来基本的插入删除操作了。
//插入操作
void insert( int x ){
int u = 0 , ic ;
for( reg i = 24 ; i+1 ; i-- ){
ic = ( x >> i ) % 2;
if( !tire[u][ic] ) tire[u][ic] = ++tot;
u = tire[u][ic];
}
word[u]++;
}
//删除操作
void delete_( int x ){
int u = 0 , ic ;
for( reg i = 24 ; i+1 ; i-- ){
ic = ( x >> i ) % 2;
u = tire[u][ic];
}
word[u]--;
}
其中 word[i] 表示以 \(i\) 结尾的数字个数。
查询 \(x\) 在当前数集中的排名
我们将所有儿子按照 0 儿子在左，1 儿子在右画图，最终会发现：对于所有的叶子节点，从左到右，代表的数字依次增大，这也是我在前面说“01Tire树是天然的有序数集容器”的原因。
这下，我们只需要检查 \(x\) 数字左边的数字个数就可以了。
注意到，如果有一个数字小于 \(x\) ，那么这个数字和 \(x\) 路径中一定存在一个公共节点，使得 \(x\) 路径向右遍历，这个数字向左遍历。
也可以理解为，倘若 \(x\) 在这个节点右转，那么在这个节点左转的所有数字一定比 \(x\) 小，因为这个数字必然在 \(x\) 的左侧。
于是我们就可以通过这个得到查询排名的方法了：遍历 \(x\) 的路径，对于路径中 \(1\) 的节点，统计这个 \(1\) 节点的兄弟 \(0\) 节点下的数字个数
最终加上1得到 \(x\) 的排名。
//查询某数的排名
int search_top( int x ){
int u = 0 , ic ;
int tp = 1 ;
for( reg i = 24 ; i+1 ; i-- ){
ic = ( x >> i ) % 2 ;
if( ic ) tp += list[ tire[u][0] ];
//如果当前儿子是1，那么加上0儿子的数字个数
u = tire[u][ic];
}
return tp;
}
其中 list[i] 表示 \(i\) 节点下的数字个数。
维护 list 数组的方法也很简单，加入操作时在每一个经过的节点上进行 list[u]++ 操作，删除时进行 list[u]-- 操作即可。
查询排名为 \(x\) 的数字。
我们从源点开始，带着我们要查询的排名 \(x\) ，我们遇到了左儿子 \(l\) ，左儿子下有 list[l] 个数字，右儿子 \(r\) ，有 list[r] 个数字。
如果有 $ x \le list[l] $ 那么证明我们要查询的数字必然在左子树中，进入左子树即可。
如果有 $ x > list[l] $ 那么我们要查询的数字在右子树中，进入右子树。
然而我们还有两个重要的事情要做：
-
因为进入了右子树，意味着我们在这一位选择了 \(1\) ,所以应该在记录路径的数字上加入
( 1 << i )。 -
因为接下来我们要在右子树中查询，不考虑左子树，所以应当对排名 \(x\) 减去左子树的数字个数，接下来的操作是 “查询右子树的第
x - list[l]名 ”。
遍历到底，我们就成功获得了排名 \(x\) 的数字，不要忘记减去 1e7 。
//查询排名为 x 的某数
int top_search( int x ){
int u = 0 , lf , rg ;
int as = 0 ;
for( reg i = 24 ; i+1 ; i-- ){
lf = tire[u][0];
rg = tire[u][1];
//lf 和 rg是两个子节点的坐标
if( list[lf] >= x && lf ) u = lf ;
//左子树直接进入即可
else if( rg ){
x -= list[lf];
as += ( 1 << i );
//减去左子树数字个数，记录1
u = rg;
}
}
return as-1e7;
//减去1e7恢复原来的数字
}
最后两个操作，查询小于（大于） \(x\) 的第一个数字。
按照我们之前的画图方法，可以看出来：
小于 \(x\) 的第一个数字，实际上就是排名为 \(x\) 排名-1 的数字，因此可以有最简单的操作方法：
- 插入 \(x\) → 查询 \(x\) 的排名 → 查询排名-1的数字并输出 → 删除 \(x\)
为了防止 \(x\) 不在当前集合中，我们先插入，查询后再删除，保证查询时 \(x\) 一定存在。
按照这样的思路，我们也可以做到查询大于 \(x\) 的第一个数字了：
- 插入 \(x\) → 查询 \(x\) 的排名 → 查询排名+
word[x]的数字并输出 → 删除 \(x\)
为了方便理解，这里word[x]暂时表示 \(x\) 这个数字的个数，代码中还是保持此前的定义。
特别的，由于我们需要调用当前数字个数，需要把 insert 函数中的根节点拿出来作为全局变量，或者直接将 insert 函数改成 int 型函数返回根节点。
//查询小于x的第一个数字
void search_before( int x ){
insert(x);
int top = search_top(x)-1;
printf("%d\n",top_search(top));
delete_(x);
}
//查询大于x的第一个数字
void search_after( int x ){
insert(x);
int top = search_top(x) + word[u_];
printf("%d\n",top_search(top));
delete_(x);
}
其中 u_ 是我们在 insert(x) 操作中维护的根节点。
终于完成了所有操作。
下面是对于时间和空间的分析。
先说结论：对于这道题，时间和空间是完全足够的。
对于时间
每一次操作，因为本质上都是遍历树，所以每次操作的复杂度是 \(O(logx)\) ，总共有 \(n\) 次操作，所以总时间复杂度为 \(O(nlogx)\) ，足以通过本题。
对于空间
01Tire树解法的一大特点就是空间换时间，与其他的算法相比，虽然思维简单许多，然而空间却是其他算法的几倍，当然，这道题所用的空间和128M的内存限制相比简直是九牛一毛，因此完全不用担心空间问题，如果实在担心空间问题的话，也有一些方法能够优化一点空间，在这里不展开了。
解析写了这么多行，完整代码我就不直接放在题解里了，我放在了云剪切板里，这里是传送门：https://www.luogu.com.cn/paste/x80142m0
代码实现的过程中有一些细节，具体可以看我代码中的注释~
希望看完这篇题解的你能够对这种非正解有所了解~
题解中如果出现问题，请私信我，我会及时进行修正。
标签：01Tire,数字,int,Luogu,list,查询,P3369,ic From： https://www.cnblogs.com/kscn/p/17643566.html