<span>模拟68 题解</span>

考试过程大概是：

上来看T1，看懂了题但是丝毫没有思路，甚至没有想到第一步贪心，心态稍崩。

接着看T2，发现似乎可以直接上主席树上树，然后想了想复杂度，直接找前趋后继，复杂度似乎很正确。

T3只会暴力。

然后就回去把T2切了，一遍过大样例自信不对拍。

结果忘了在线这回事，一个小时之后才发现。

接着回去看T1，发现也是数据结构，然后又打了一个主席树干掉了，自信也不打对拍。

只会打T3暴力，尝试用位运算的性质，然后推出了55分，稍微优化一下就有75分了。

三道数据结构题，对数据结构选手非常友好，就非常kx。

然后还有半个多小时就对拍了下T3，过了下T1T2极限数据等死了。

显然将矩形的左上角都平移到同一个点，不会使答案更差。

尝试枚举最后交集矩形的长度$a$，设为$a_x$。

那么，对于任意$a_i$<$a_x$，应当被删掉，设删掉了$cnt$个。

若$cnt>m$，那么不合法。否则剩余了$m-cnt$个删除机会。

可以将$a_i>=a_x$中$b_i$最小的$m-cnt$个删掉，所以问题其实是区间第$m-cnt+1$小的元素。

显然主席树是可以解决的，一些其它简单数据结构也没有问题。

因为最近才看见过类似的数据结构，一眼主席树上树。

意思大概是每个点继承它父亲的信息，然后就可以快速地访问一条链上的信息。

本题中只要取$k$个点的$lca$，并将$k$个点分别查询该点到$lca$这条链上$r$的前趋后继就可以了。

查询方法是在主席树上搜索。

以查询后继为例：

如果左儿子合法，那么先搜索左儿子。

否则搜索右儿子。

显然这个复杂度不会超过$O(log^2n)$，因为如果找出合法区间，对于每个区间直接向下走一条链是$O(log^2)$的。

如果左儿子搜到信息就不再搜索右儿子，复杂度是$O(logn)$的。

因为主席树上的节点，最多存在一个搜索了左右两个儿子。

也就是说只搜索了两条链。

考虑怎样的点对$(i,j)$，异或后会形成逆序对。

因为异或是位运算，所以尝试将$a_i\ a_j$二进制分解。

对于两个元素高位相同的01串，我们并不在意。

在意的是从高到低第一位不同的数。

如果这个数表现为$(0,1)$，即$a_i$在此位为0，$a_j$在此位为1。

那么该位异或1之后会形成逆序对，异或0之后一定不会形成逆序对，因为后面的数无论相差多少，也补偿不回来。

如果这个数表现为$(1,0)$，形式是类似的。

所以问题是求二进制下每一位开始不同的数对个数。

显然可以用$01trie$树简单处理。

然而之后暴力枚举，复杂度仍然是$2^k$的。

题中的$spj$实际上提示了我们可以进行二分，

事实上二分很可行，因为排名显然关于二元组单调。然而似乎$check$并没有那么简单。

这里又用到了一个很巧妙的思想：$meet\ in\ the\ middle$。

策略是：将$k$分为两部分，$k_1$表示$k$的高位，$k_2$表示$k$的低位。

因为两部分是互不干预的，将两部分的答案分别预处理出来。

先考虑第一问第$p$小逆序对个数，设当前二分的值为$mid$，

枚举高位会贡献多少个逆序对，设为$l_i$，那么低位最多贡献逆序对个数为$mid-l_i$。

只要二分出低位第一个大于$mid-l_i$的元素的下标就可以了。

第二问是类似的。

在二分出第一问的答案之后，可以继续二分第二问的答案。

高位和地位的二元组拼在一起，可以拼成答案二元组。

二分答案二元组，通过枚举高位二元组，自然也可以二分找到最大的合法的低位二元组。

题解的做法更加巧妙一点，因为高位二元组和低位二元组都是单调的，直接双指针就可以了。

应云力云力要求，放上本题代码

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cstring>
 6 using namespace std;
 7 const int N=5e5+7;
 8 int n,k,p,mx,ptr=1,k1,k2,lim1,lim2;
 9 int val[N];
10 int bin[35],sz[N*32],ch[N*32][2];
11 long long add[35][2];
12 vector<pair<long long,long long>> a,b;
13 inline void insert(int x){
14     int p=1;
15     for(int i=k-1;~i;--i){
16         if(x&bin[i]){//这一位为1
17             add[i][1]+=sz[ch[p][0]];
18             if(!ch[p][1]) ch[p][1]=++ptr;
19             p=ch[p][1]; ++sz[p];
20         }
21         else{
22             add[i][0]+=sz[ch[p][1]];
23             if(!ch[p][0]) ch[p][0]=++ptr;
24             p=ch[p][0]; ++sz[p];
25         }
26     }
27 }
28 inline int read(register int x=0,register char ch=getchar(),register int f=0){
29     while(!isdigit(ch)) f=ch=='-',ch=getchar();
30     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
31     return f?-x:x;
32 }
33 inline int calc(long long x,long long y=0x7f7f7f7f7f,int ans=0){//小于等于x的答案
34     for(int i=0;i<a.size();++i) ans+=upper_bound(b.begin(),b.end(),make_pair(x-a[i].first,y-a[i].second*lim2))-b.begin();
35     return ans;
36 }
37 int main(){
38     //freopen("f3.in","r",stdin);
39     n=read(); k=read(); p=read(); mx=1<<k;
40     for(int i=0;i<32;++i) bin[i]=1<<i;
41     for(int i=1;i<=n;++i) insert(val[i]=read());
42     k1=k>>1; k2=k+1>>1;
43     lim1=1<<k1; lim2=1<<k2;
44     for(int i=0;i<lim1;++i){
45         pair<long long,long long> it=make_pair(0,i);
46         for(int j=k1-1;~j;--j) it.first+=add[j+k2][(i>>j)&1];
47         a.push_back(it);
48     }
49     for(int i=0;i<lim2;++i){
50         pair<long long,long long> it=make_pair(0,i);
51         for(int j=k2-1;~j;--j) it.first+=add[j][(i>>j)&1];
52         b.push_back(it);
53     }
54     sort(a.begin(),a.end());
55     sort(b.begin(),b.end());
56     long long l=0,r=1ll*n*(n-1)/2,ans1=l;
57     while(l<r){
58         long long mid=l+r>>1;
59         if(calc(mid)<p) l=mid+1;
60         else r=mid;
61     }
62     printf("%lld ",ans1=l);
63     l=0; r=mx-1;
64     while(l<r){
65         long long mid=l+r>>1;
66         if(calc(ans1,mid)<p) l=mid+1;
67         else r=mid;
68     }
69     printf("%d\n",l);
70     return 0;
71 }

T3 二分套二分

模拟68 题解

A. d

B. e

C. f