Greater and Greater（bitset） 2020牛客暑期多校训练营（第二场）

本文主要是介绍Greater and Greater（bitset） 2020牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：
看题解的时候可以结合这篇博客

首先我们要搞清楚维护的是啥。
我们对每一个 $a [i]$ 维护一个 $m$ 位的bitset，表示 $a [i]$ 是否大于 $b [j]$ 。
这样的 $b i t s e t$ 最多只有 $m$ 种，因为 $b$ 数组就m个数字，这个有单调性。
所以我们可以预处理出这 $m$ 种 $b i t s e t$ ，然后 $a [i]$ 在 $b$ 中二分一下就知道其对应的 $b i t s e t$ 了。

维护好了每一个 $a [i]$ 的 $b i t s e t$ 对应的A[i]，我们再维护一个新的 $b i t s e t < m a x m > c u r [m a x n]$ ，
则有
$cur[i][0]=A[i][0]\&cur[i+1][0]\&cur[i+2][0]\&...\&cur[i+m-1][0]$
$cur[i][1]=A[i][1]\&cur[i+1][1]\&cur[i+2][1]\&...\&cur[i+m-2][1]$
$cur[i][2]=A[i][2]\&cur[i+1][2]\&cur[i+2][2]\&...\&cur[i+m-3][2]$
.
.
.
$c u r [i] [m - 1] = A [i] [m - 1]$

我们仅考虑 $c u r [i]$ 的第0位，可以看到当其全是0的时候，表示 $A [i + m - 1] [m - 1] = 1, A [i + m - 2] [m - 2] = 1, A [i + m - 3] [m - 3] = 1, . . ., A [i] [0] = 1$ ，所以是合理的答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <bitset>
#include <iostream>using namespace std;typedef long long ll;const int maxn = 2e5 + 7;
const int maxm = 4e4 + 7;int a[maxn],b[maxn],order[maxn];
bitset<maxm>cur,B[maxn];
int n,m;int Find(int x) {int l = 0,r = m;int ans = l;while(l <= r) {int mid = (l + r) >> 1;if(b[order[mid]] <= x) {l = mid + 1;ans = mid;} else {r = mid - 1;}}return ans;
}int cmp(int x,int y) {return b[x] < b[y];
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}for(int i = 1;i <= m;i++) {scanf("%d",&b[i]);order[i] = i;}sort(order + 1,order + 1 + m,cmp);for(int i = 1;i <= m;i++) {B[i] = B[i - 1];B[i].set(order[i] - 1);}int ans = 0;for(int i = n;i >= 1;i--) {cur >>= 1;bitset<maxm>now = B[Find(a[i])];cur &= now;if(a[i] >= b[m]) {cur.set(m - 1);}ans += cur[0];}printf("%d\n",ans);return 0;
}