【Newcoder】2020牛客暑期多校训练营（第二场）G - Greater and Greater | bitset、思维

题目链接：https://ac.nowcoder.com/acm/contest/5667/G

题目大意：

给出长度为n的A序列和长度为m的B序列

问A序列中有多少个长度为m的子区间使得对于区间内每个数都满足A>=B

题目思路：

学习新思想，争做新青年

bitset教做人系列

之前也遇到很多bitset的题，bitset也确实挺好用。

对于B中元素每一个都求一个位置的bitset大小为N

假设

A：4 5 1 2 3

B：1 2 3

那么用1代表A大于等于B，0代表A小于B

可知:

B_1 = 1 1 1 1 1

B_2 = 1 1 0 1 1 

B_3 = 1 1 0 0 1

那么很容易得出一个结论，得到的这个M*N的矩阵有多少个斜着长度为m的全是1的线，就是答案ans

之后做一个转换，考虑倒数第一行的数全部有用，倒数第二行最后一个数没用，倒数第三行最后两个数没用，如图：

 所以将第一行右移两个，第二行右移一个，最后三者与起来，看有几个是1就好了

Note:计算机储存和样例不同，计算储存高位在右，所以程序应该向左移。

那么关键问题就在于如何计算这个B矩阵

我们发现只需要一个bitset就够了，我们A，B都降序排序之后。大于当前的一定也大于之后的

所以n+m的复杂度就可以处理B矩阵，之后答案进行与时bitset降16~32复杂度：

总体:

Code：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define rep(i,n) for(int i=1;i<=(n);i++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =2e5+10;
const int mod=998244353;
const int Mod = 1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
pair<ll,ll>a[maxn],b[maxn];
bitset<maxn>ans,bs;
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(a[i].first);
        a[i].second = i;
    }
    for(int i=1;i<=m;i++){
        read(b[i].first);
        b[i].second = i;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    ans.set();
    for(int i=m,j=n;i>=1;i--){
        while(j>=1&&b[i].first<=a[j].first){
            bs.set(a[j].second-1);
            j--;
        }
      //  for(int k=1;k<=n;k++) printf("%d ",bs.test(k));
        ans &= bs<<(m-b[i].second);
      //  printf("\n");
    }
    printf("%d\n",ans.count());
    return 0;
}
/**
0 1 1 1 1 1
0 1 0 1 1 1
0 1 0 1 1 1
**/