Weak Pair 离散化+树状数组
Source
博客里只记录了今天网络赛自己过的题， 队友过的题就不整理上来了 Y ( ^ - ^ ) Y
离散化+树状数组
把祖先节点的值 作为下标 插入的树状数组里， 即 val 的位置插入一个 1， add(val, 1)，
然后到当前位置是 get(k / val) 就是 当前满足条件的祖先节点，
回溯的时候把当前的祖先节点pop掉， 即 在 val 位置 插入 一个 -1 ， add(val, -1) 这样 就可以维护成 树状数组里记录的 都是当前节点的祖先节点 也是 所有祖先节点。
然后就是 val < 1e9， 直接使用 树状数组必然不行， 所以 我们 进行离散化， 把 n 个 val[i] 和 n 个 k / val[i] (其中 val[i] > k 时 直接 把 val[i] push 进去， 然后最后 这些 祖先节 点 不考虑的)，
sort(Ind.begin(),Ind.end());
Ind.erase(unique(Ind.begin(),Ind.end()), Ind.end());
int sz = Ind.size();
for(int i = 0; i < sz; i++)
mp[Ind[i]]=i+1;
遍历节点 复杂度 O(n)， 使用 树状数组 每次 O(logn)
故 复杂度 O(nlogn)
#include
#include
#include
#include
非特殊说明，本博所有文章均为博主原创，未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
共有 0 条评论