模拟68 题解

考试过程大概是:

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

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

T3只会暴力。

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

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

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

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

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

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

 

A. d

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

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

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

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

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

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

 

 

 

B. e

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

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

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

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

以查询后继为例:

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

否则搜索右儿子。

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

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

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

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

 

 

 

C. f

考虑怎样的点对$(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
 2 #include
 3 #include
 4 #include
 5 #include
 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 vectorlong 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;ib.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<1<<k2;
44     for(int i=0;ii){
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;ii){
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)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)1;
67         else r=mid;
68     }
69     printf("%d\n",l);
70     return 0;
71 }
T3 二分套二分

 

你可能感兴趣的