这题做法很多
可以通过类似noi超级钢琴那道题目的做法用可持久化+trie来做还可以直接在trie树上维护size域然后类似查找k大的做法做总之还是比较水的
1 type node=record 2 kth,num,ans:longint; 3 end; 4 5 var heap:array[0..100010] of node; 6 son:array[0..3000010,0..1] of longint; 7 size:array[0..3000010] of longint; 8 a:array[0..100010] of longint; 9 t,i,n,m:longint; 10 11 procedure swap(var a,b:node); 12 var c:node; 13 begin 14 c:=a; 15 a:=b; 16 b:=c; 17 end; 18 19 procedure add(x:longint); 20 var i,p,y:longint; 21 begin 22 p:=1; 23 for i:=30 downto 0 do 24 begin 25 y:=x and (1 shl i); 26 if y>1 then y:=1; 27 if son[p,y]=0 then 28 begin 29 inc(t); 30 son[p,y]:=t; 31 end; 32 p:=son[p,y]; 33 inc(size[p]); 34 end; 35 end; 36 37 function ask(x,k:longint):longint; 38 var p,i,y:longint; 39 begin 40 p:=1; 41 ask:=0; 42 for i:=30 downto 0 do 43 begin 44 y:=x and (1 shl i); 45 if y>1 then y:=1; 46 if size[son[p,y]]>=k then p:=son[p,y] 47 else begin 48 ask:=ask+1 shl i; 49 k:=k-size[son[p,y]]; 50 p:=son[p,1-y]; 51 end; 52 end; 53 end; 54 55 procedure sift(i:longint); 56 var j:longint; 57 begin 58 j:=i shl 1; 59 while j<=t do 60 begin 61 if (j+1<=t) and (heap[j].ans>heap[j+1].ans) then inc(j); 62 if heap[i].ans>heap[j].ans then 63 begin 64 swap(heap[i],heap[j]); 65 i:=j; 66 j:=i shl 1; 67 end 68 else break; 69 end; 70 end; 71 72 begin 73 readln(n,m); 74 t:=1; 75 for i:=1 to n do 76 begin 77 readln(a[i]); 78 add(a[i]); 79 end; 80 for i:=1 to n do 81 begin 82 heap[i].num:=a[i]; 83 heap[i].kth:=2; 84 heap[i].ans:=ask(a[i],2); 85 end; 86 t:=n; 87 for i:=n div 2 downto 1 do 88 sift(i); 89 for i:=1 to 2*m do 90 begin 91 if i mod 2=1 then write(heap[1].ans,' '); //注意会被重复计算 92 if heap[1].kth=n then 93 begin 94 swap(heap[1],heap[t]); 95 dec(t); 96 end 97 else begin 98 inc(heap[1].kth); 99 heap[1].ans:=ask(heap[1].num,heap[1].kth);100 end;101 sift(1);102 end;103 end.