题解 (by;zjvarphi)
对于一个数，如果它二进制下第 (i) 位为 (1)，那么 ( m x) 在这一位选 (1) 的贡献就是和它不同的最高为为 (i) 的数的个数
这个东西很好搞，整一个 ( m 01trie) 就行，每会插入的时候直接统计即可
但是如何求第 (p) 位，二分，但每回二分时 (2^k) 搜索一遍就超时了，( m meet;in;the;middle)
发现每一位是相互独立的，也就是说它们之间是不会互相影响的，所以将二进制位割半，分别排个序，之后对于一个序列用指针从小往大搜，同时维护另一个指针，而这个指针一定是单调递减的;
所以复杂度就是 (2^frac{k}{2}logfrac{n×(n-1)}{2})
对于第二问，对于大的那一半开个桶，维护它能在小的那一半匹配上的数，最后按大的排序，跳区间，每次判断这个数匹配上的 (siz) 是否大于 (p)，若大于就在区间内暴力，可以保证复杂度不会超过 (2^frac{k}{2})
所以总复杂度为 (mathcal O m (nk+2^frac{k}{2}logfrac{n×(n-1)}{2}+2^frac{k}{2}))
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define pb(x) push_back(x)
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=5e5+7;
int a[N],tmp[N],st[N],pg[1<<16],id[1<<16],cnt1,cnt2,cnt,n,k,p,mx,hk,kh,S1,S2,bs,num,ans;
ll al,del[33];
vector<int> sg[1<<16];
struct slv{ll f;int id;}so1[1<<16],so2[1<<16];
inline int operator<(const slv &s1,const slv &s2) {return s1.f<s2.f;}
struct BIT{
#define lowbit(x) ((x)&-(x))
int c[N];
inline void update(int x) {for (ri i(x);i<=mx;i+=lowbit(i)) p(c[i]);}
inline int query(int x) {
int res(0);
for (ri i(x);i;i-=lowbit(i)) res+=c[i];
return res;
}
}B;
struct Trie{
#define sn(x,u) T[x].ch[u]
struct trie{int ch[2],sz;}T[N*30];
int tot;
Trie(){tot=1;}
inline void insert(int nw) {
int p=1;
for (ri i(29);~i;--i) {
ri cur=(nw>>i)&1;
if (!cur) del[i]-=T[sn(p,cur^1)].sz;
else del[i]+=T[sn(p,cur^1)].sz;
if (!sn(p,cur)) sn(p,cur)=p(tot);
p=sn(p,cur);
p(T[p].sz);
}
}
}T;
inline void init() {
sort(tmp+1,tmp+n+1);
int k=unique(tmp+1,tmp+n+1)-tmp;
for (ri i(1);i<=n;p(i)) st[i]=lower_bound(tmp+1,tmp+k,st[i])-tmp;
mx=k-1;
for (ri i(n);i;--i) {
al+=B.query(st[i]-1);
B.update(st[i]);
}
}
inline int check(ll f) {
ri p2=1;
num=0;
for (ri p1(cnt1);p1;--p1) {
while(p2<=cnt2&&so2[p2].f+so1[p1].f+al<=f) p(p2);
num+=p2-1;
}
return num>=p;
}
inline void checka(ll f) {
ri p1=1,tmp;
num=0;
for (ri p2(cnt2);p2;--p2) {
p(cnt);
id[pg[cnt]=cnt]=so2[p2].id;
while(p1<=cnt1&&so2[p2].f+so1[p1].f+al<f) p(p1);
tmp=0;
while(p1<=cnt1&&so2[p2].f+so1[p1].f+al==f) {
p(tmp);
sg[cnt].pb(so1[p1].id);
p(p1);
}
num+=p1-1-tmp;
}
}
inline int cmp(int x,int y) {return id[x]<id[y];}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(k),read(p);
for (ri i(1);i<=n;p(i)) read(a[i]),st[i]=tmp[i]=a[i];
init();
for (ri i(1);i<=n;p(i)) T.insert(a[i]);
hk=k>>1,kh=k-hk;
bs=(S1=(1<<hk)-1)+1;
S2=((1<<kh)-1)<<hk;
for (ri i(0);i<=S1;p(i)) {
ll tmp=0;
for (ri j(0);j<hk;p(j)) if ((i>>j)&1) tmp+=del[j];
so1[p(cnt1)].f=tmp;
so1[cnt1].id=i;
}
for (ri i(0);i<=S2;i+=bs) {
ll tmp=0;
for (ri j(hk);j<k;p(j)) if ((i>>j)&1) tmp+=del[j];
so2[p(cnt2)].f=tmp;
so2[cnt2].id=i;
}
sort(so1+1,so1+cnt1+1);
sort(so2+1,so2+cnt2+1);
ll l=0,r=(ll)n*(n-1)/2,res(0);
while(l<=r) {
ll mid=(l+r>>1ll);
if (check(mid)) r=mid-1,res=mid;
else l=mid+1;
}
checka(res);
sort(pg+1,pg+cnt+1,cmp);
p-=num;
for (ri i(1);i<=cnt;p(i)) {
int cur=pg[i],siz=sg[cur].size();
if (p>siz) p-=siz;
else {
sort(sg[cur].begin(),sg[cur].end());
ans=id[cur]|sg[cur][p-1];
break;
}
}
printf("%lld %d
",res,ans);
return 0;
}
}
int main() {return nanfeng::main();}