ACM 牛客2020暑期多校G题Greater and Greater

标签: 牛客多校赛  算法  acm竞赛  数据结构  c++

题意

链接:Greater and Greater

给两个数组A[n],B[m],求A的长度为m的子区间,使其中的每个数都大于B中对应的数。

(1≤n≤150000,1≤m≤min{n,40000})
输入
6 3
1 4 2 8 5 7
2 3 3

输出
2

说明
The two subintervals are {[2, 8, 5], [8, 5, 7]}[2,8,5],[8,5,7].

题解

官方题解

Alt

我的补充解释(可能提出的问题)

花了两个小时自认为看明白的东西,面向难以理解细节的小白。

为什么本质上只有O(m)种不同的bitset?

因为他构造的bitset——Si,实质上表示的是某个数大于等于B中数的个数,比如B[] = {3,2,4},任何一个数只能大于等于其中0-3个数。比如1,比任意一个B中的数都小,所以它会对应S0,S0中全都是0;再比如3,它大于等于B中的两个数,所以它会对应S2,S2中会有两个1。而这1的具体位置,后面会再讲。因此如果每个Si中i只代表1的个数的话,最后Si的种类只会有m+1种。相信你还会有疑惑,为什么不用考虑排列关系?后面会给1的位置定规则。

为什么要排序?为什么可以排序?

这里的排序其实没有直接排B,而是把他的对应下标拿出来排序了,比如B[] = {3,2,4},原来的下标ord[] = {0,1,2},排序后得到ord[] = {1,0,2},给了一个后面对B二分的途径,又没有改变B中原有的位置关系。后面的二分是为了找A大于了多少个B中的元素,方便找到对应的Si。

Si中1的位置规则?

Si除了新增的那一位,剩下的都和Si-1相等,新增的位置按照ord[]的位置置1。这里可能结合样例会好懂一些。(Bs[i]代表Si)
首先根据ord[0] = 1,得到Bs[1] = 010(注意bitset中的下标是从右往左排的),依此类推得到Bs[2] = 011,Bs[3] = 111。
这里的每个Bs其实对应了一个使能关系,代码中ans += cur[0],cur[0]这个数刚开始一定是从cur[m-1]来的,它跑到cur[0]的过程,算上自己其实经历了m次验证,也就是对应着,以它为区间右端点时,A[i]~A[i-m+1]中所有数,都是经过和Bs的与运算验证的(它本身的验证为刚开始就验证了的if语句)。

for (int i = n - 1; i >= 0; i --)
{
	cur >>= 1;
	cur &= Bs[GetRank(A[i])];
	if (A[i] >= B[m - 1])
		cur.set(m - 1);
	ans += cur[0];
}

在这里插入图片描述

为什么前面我们这样的方法得到的Bs[i]通过与运算可以承担验证功能?

首先我们找到的Bs[i],说明了这个数在对应位置是否比B[i]中的数大,比如有一个数2,按照前面的找法会对应Bs[1] = 010,也就是说2可以放在第1位,因此它第1位的值是1,而0,2的值都是0,也就是说,当它加入要比较中的串中时,它会使以它为第0,2位的对应cur为0,在例子中对应的就是5被否了,因为在5为最右边的数时,2在第2位。而8对应的1还是1,说明在2加入时以它为最右边的数时,2在第1位,是可行的,此时如果后面的数加入后依旧可行,则以8为右端点的子区间是可行的。

解决了这些问题,应该可以理解官方给的标程了

#include <bitset>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 150000 + 5
#define M 40000 + 5

int n, m, ans, A[N], B[M], Ord[M];
bitset<M> cur, Bs[M];

int GetRank(int x)    								    //对每一个A[i],都找到对应的Bs
{
	int l = 0, r = m;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (x < B[Ord[mid]])       						//对Ord排序了,所以可以通过Ord对B进行二分查找
			r = mid;
		else l = mid + 1;
	}
	return l;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i ++)
		scanf("%d", A + i);
	for (int i = 0; i < m; i ++)
	{
		scanf("%d", B + i);
		Ord[i] = i;
	}
	sort(Ord, Ord + m, [](int u, int v) {				//根据B对Ord排序
		return B[u] < B[v];
	});
	for (int i = 1; i <= m; i ++)
	{
		Bs[i] = Bs[i - 1];
		Bs[i].set(Ord[i - 1]);
	}
	for (int i = n - 1; i >= 0; i --)
	{
		cur >>= 1;
		cur &= Bs[GetRank(A[i])];						//A[i]进入序列时对右边的所有点都判断了,作为右端点时是否可行
		if (A[i] >= B[m - 1])							//判断了自己作为右端点时是否可行
			cur.set(m - 1);
		ans += cur[0];				·					//cur从m-1到0的过程中,如果所有新塞进去的数都在对应位置都可行,最后cur[0]就会为1,作为判断依据
	}
	printf("%d\n", ans);
	return 0;
}

有错误欢迎指正

版权声明:本文为qq_44869819原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44869819/article/details/107365808