2020牛客多校第二場（G題）Greater and Greater

題目描述：給定大小為n的序列A和大小為m的序列B，計算A中所有大小為m的子區間S，滿足

S i > = B i 1 < = i < = m S_{i} >= B_{i} {1 <= i <= m } Si​>=Bi​1<=i<=m

f 是 a 中哪些位置的數大于等于目前數。如果大于 置為1，

ans 就是哪些位置滿足條件， ans[i] 代表區間 [i, i + m], 是不是滿足條件。

用 bitset 搞一下，

直接暴力肯定是不行的，

然後我們考慮到每一個 b[i], 它會影響哪些 s[i], s[i] 代表 a[i] - a[i+m],

隻有 a 中的大于等于 b[i] 的數， 這些數對應的 s[i] 才能為1， 否則為0， 為0就代表s[i] 不滿足條件。

是以我們對 a 和 b 從大到小排序， 帶着下标一起，

枚舉 b 的值x， 把 a 中大于等于 x 的值的下标在 f 中标記一下， 在枚舉下一個值的時候，之前的值肯定大于目前的值，因為是從大到小排序的。

目前的枚舉的 i ， 他在b數組中的位置就是 b[i].pos, 那麼它就會影響 ans[1] - ans[ n - b[i].pos] 的值。

公式就是：

ans &= f >> b[i].pos

思考：

對于這樣的題， 整體上不太會，

那麼就要考慮個體對于整體的影響，

考慮每一個個體，它和整體是什麼關系。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
bitset<N>ans,f;
void dbg() {cout << endl;}
template<typename T, typename... A> void dbg(T a, A... x) {cout << a << ' '; dbg(x...);}
#define logs(x...) {cout << #x << " -> "; dbg(x);}
struct node{
    int pos, x;
    bool operator < (const node &A) const {
        return x > A.x;
    }
}a[N],b[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i)
        scanf("%d",&a[i].x), a[i].pos = i;
    for (int i = 1; i <= m; ++i)
        scanf("%d",&b[i].x), b[i].pos = i;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    ans.set(); f.reset();

    for (int i = 1, j = 0; i <= m; ++i){
        while((j+1) <= n && a[j+1].x >= b[i].x){
            f[a[j+1].pos] = 1;
            j++;
        }
        ans &= (f >> b[i].pos);
    }
    printf("%d\n",(int)ans.count());
    return 0;
}