本文共 1395 字，大约阅读时间需要 4 分钟。

注：xor对应于pascal中的“xor”，C++中的“^”。

思路：同NOI2010超级钢琴。

我们只需一开始在全局堆中放进去每个数和他之后的数异或的最小值，然后在每次出堆的的时候再放进堆中第k+1小值即可。这样重复k次。

那么问题就变成了快速求某段区间给定一个数进行xor的第k小值，我们利用可持久化trie维护size直接在树上二分即可。

时间复杂度依旧O(klogn).

Code:

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std; #define N 100010int w[N]; int ch[N<<5][2], size[N<<5], ind;int root[N];int Newadd(int Last, int bit, int x) {    int q = ++ind;    ch[q][0] = ch[Last][0], ch[q][1] = ch[Last][1];    size[q] = size[Last] + 1;         if (bit < 0)        return q;         if ((x >> bit) & 1)        ch[q][1] = Newadd(ch[Last][1], bit - 1, x);    else        ch[q][0] = Newadd(ch[Last][0], bit - 1, x);    return q;}int getkth(int Left, int Right, int x, int k) {    int res = 0, better;    bool d;    for(int dep = 30; dep >= 0; --dep) {        d = (x >> dep) & 1;        better = size[ch[Right][d]] - size[ch[Left][d]];        if (better >= k)            Left = ch[Left][d], Right = ch[Right][d];        else            Left = ch[Left][d ^ 1], Right = ch[Right][d ^ 1], res += (1<
       
        >= 1)            if (a[x]
        
         >1]) swap(a[x],a[x>>1]); else break; } inline void down(int x) { int son; for(; (x<<1)<=top; ) { son=(((x<<1)==top)||(a[x<<1]
         
          <<1)|1]))?(x<<1):((x<<1)|1); if (a[son]
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/wyfcyx_forever/article/details/40400287 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！