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

暴力很简单，复杂度：On*m =6e9；

这个复杂度比较容易想到bitset(虽然我没想到，但做过这种题就很容易想到了)

优化为：O(n*m/32)=2e8 完全可以接受。

那么我们考虑如何用bitset来做：

对于样例：

1 4 2 8 5 7
2 3 3

b[1]=2时：

我们维护一个bitset：

011111 , 表示 a[i]是否大于等于b[1]。

对于b[2],b[3]同样维护：则三个bitset分别为：

011111

010111

010111

而我们要找的是一个子区间，对于每一位都有：S[i]>=b[i],

在我们的bitset里表现为：一个↘使得线上的元素都为1，

比如样例：

011111

010111

010111

有两条↘满足，则满足题意的子区间有2个。

这种斜线显然不是很好处理，我们可以利用bitset的特性：可以<<,>>操作把b[i]表示的bitset左移 (i-1)位，则bitset表现为：

011111

101110

011100

注意这里会有被消为0的元素，这些元素要么是往前无法凑成一个长度为m的区间，要么往后无法凑成长度为m的区间。

而现在我们只需要找多少条竖线满足：竖线上元素均为1。  这里直接把所有bitset与起来即可( & ) 。 最后得到的bitset中1的数量就是结果。

那么如何构造出m个bitset呢？如果是暴力判断结果还是Onm的复杂度。

我们可以这样做：(类似于尺取/滑动窗口的思想)

先把ab数组从小到大排序：(以样例为例)

124578

233

b[1]:011111

b[2]:001111

b[3]:001111

可以发现：b数组从小到大，是有继承关系的，先暴力求出b[1]的bitset，然后b[2]继承b[1],其中与b[1]不同的是：所有a中元素

大于等于b[1]小于b[2]的元素的位置在b[2]里的值为0.

这样构造出m个bitset的复杂度为：O(n+m),bitset的操作复杂度为：O(n*m/32)完全可以接受。

这里排序ab数组时用结构体记录下原来的位置，对应位置即可。

具体细节看代码。代码中bitset是右移，这是为了方便赋值判断。(即元素从右往左插入bitset里)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI= acos(-1.0);
const int M = 2e5+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
struct node{
	int x,id;
}a[M],b[M];
bool cmp(node a,node b)
{
	return a.x<b.x;
}
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	int n,m;
  	cin>>n>>m;
  	for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;
  	for(int i=1;i<=m;i++)cin>>b[i].x,b[i].id=i;
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+m,cmp);
	bitset<150007>s,tp,ans;
	int ap=n;
	for(int i=n;i>=1;i--)if(a[i].x>=b[1].x)s[a[i].id]=1,ap=i;
	tp=s;tp>>=(b[1].id-1);
	ans=tp;
//	cout<<s<< "    -     "<<tp<<"     =    "<<ans<<endl;
	for(int i=2;i<=m;i++)
	{
		while(a[ap].x<b[i].x)s[a[ap].id]=0,ap++;
		tp=s;
		tp>>=(b[i].id);
		ans&=tp;
	//	cout<<s<< "    -     "<<tp<<"     =    "<<ans<<endl;
	}
	cout<<ans.count()<<endl;
	return 0;
}