BZOJ 3689: 异或之

字典树可以$o(logn)查找第k大$

使用$可持久化Trie 区间查找第k大，然后首先把每个数异或之后的最小丢进小根堆中，然后一个一个取出，取出后就再丢次小，一共取k次$

总的时间复杂度为$O(klogn)$

本来的考虑是 先找出第k大，然后在$Trie上DFS把小于这个数的全丢进vector  然后发现会有很多无用状态会搜索到，T掉$

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int n, k, arr[N], kth;

 struct node

 {

     int base, num, pos, l, r;

     node () {}

     node (int base, int num, int pos, int l, int r) : base(base), num(num), pos(pos), l(l), r(r) {}

     bool operator < (const node &r) const { return num > r.num; }

 };

 priority_queue <node> q;

 namespace TRIE

 {

     int rt[N], cnt;

     struct node

     {

         int son[], cnt;

     }a[N * ];

     void init()

     {

         a[].son[] = a[].son[] = a[].cnt = ;

         cnt = ;

     }

     void insert(int &now, int pre, int x)

     {

         now = ++cnt;

         a[now] = a[pre];

         int root = now; ++a[root].cnt;

         for (int i = ; i >= ; --i)

         {

             int id = (x >> i) & ;

             a[++cnt] = a[a[root].son[id]];

             ++a[cnt].cnt;

             a[root].son[id] = cnt;

             root = cnt;

         }

     }

     int find_kth(int x, int k, int l, int r)

     {

         int res = ;

         int tl = rt[l], tr = rt[r];

         for (int s = ; s >= ; --s)

         {

             int id = (x >> s) & ;

             int sum = a[a[tr].son[id]].cnt - a[a[tl].son[id]].cnt;

             if (sum < k)

             {

                 k -= sum;

                 res |=  << s;

                 tr = a[tr].son[id ^ ];

                 tl = a[tl].son[id ^ ];

             }

             else

             {

                 tr = a[tr].son[id];

                 tl = a[tl].son[id];

             }

         }

         return res;

     }

 }

 int main()

 {

     while (scanf("%d%d", &n, &k) != EOF)

     {

         for (int i = ; i <= n; ++i) scanf("%d", arr + i);

         TRIE::init();

         for (int i = ; i <= n; ++i) TRIE::insert(TRIE::rt[i], TRIE::rt[i - ], arr[i]);

         for (int i = ; i < n; ++i) q.push(node(arr[i], TRIE::find_kth(arr[i], , i, n), , i, n));

         for (int i = ; i <= k; ++i)

         {

             node top = q.top(); q.pop();

             printf("%d%c", top.num, " \n"[i == k]);

             q.push(node(top.base, TRIE::find_kth(top.base, top.pos, top.l, top.r), top.pos + , top.l, top.r));

         }

     }

     return ;

 }