2020牛客多校第二场 G - Greater and Greater（思维+bitset）

传送门

---

题目大意

给出一个长度为 n n n的序列 A A A，一个长度为 m ( m ≤ n ) m(m \leq n) m(m≤n)的序列 B B B，问序列 A A A有多少长度为 m m m的连续子序列 S S S使得 ∀ i ∈ [ 0 , m ) ， S i ≥ B i \forall i \in [0,m)，S_i \geq B_i ∀i∈[0,m)，Si​≥Bi​

解题思路

参考了如下博客链接，十分感谢！

这样转化问题的方式真的很神奇，对每个 B i B_i Bi​遍历 A A A数组得到每个数相对于 B i B_i Bi​的大小（用 0 , 1 0,1 0,1表示）例如样例 A = 1 , 4 , 2 , 8 , 5 , 7 A={1,4,2,8,5,7} A=1,4,2,8,5,7：

B [ 0 ] = 2 ： 011111 B[0]=2：011111 B[0]=2：011111
B [ 1 ] = 3 ： 010111 B[1]=3：010111 B[1]=3：010111
B [ 2 ] = 3 ： 010111 B[2]=3：010111 B[2]=3：010111

然后从序列 A A A的一个位置 j j j向后遍历 m m m个数的过程，实际上就是对于序列 A A A的 [ 0 , n − m ] [0,n-m] [0,n−m]的位置，从上述第一个01序列开始斜着向右下角走 m m m次，若这些位置全为 1 1 1，那么可以对答案产生贡献。

然后我们又可以发现，第 i    ( i ∈ [ 0 , m )   ) i~~(i \in[0,m)~) i  (i∈[0,m) )个01序列左边的 i i i个数是没有用的，那么我们可以对每个 01 01 01序列左移 i i i位，右边补0：

011111 011111 011111
101110 101110 101110
011100 011100 011100

这样对这些 01 01 01序列作与运算，最后看有多少位仍为 1 1 1即可，显然这一过程使用bitset会极其方便。现在唯一的问题是如何快速对每个 B j   ( j ∈ [ 0 , m )    ) B_j~(j \in[0,m)~~) Bj​ (j∈[0,m)  )求出其中有多少 A i ( i ∈ [ 0 , n )    ) A_i(i \in[0,n)~~) Ai​(i∈[0,n)  )小于 B j B_j Bj​并将 b i t s e t bitset bitset的对应位置零。假设当前操作的是 A k < B j A_k < B_j Ak​<Bj​，那么小于等于 A k A_k Ak​的数显然不需要操作，大于 B j B_j Bj​的其他的 B ? B_? B?​也不需要操作，于是，我们可以对序列 A , B A,B A,B分别排序，然后记录每个元素的位置，这样只需要 O ( n + m ) O(n+m) O(n+m)的时间复杂度即可遍历所有的数，而且只需要维护更新一个01序列。

PS： b i t s e t bitset bitset的01串是从右向左存储的，也就说最右端是最低位，那么上述左移在bitset中要右移

代码跑的很快，事实证明即使是 1 e 5 1e5 1e5数量积的bitset作位运算的常数也是很小的。

//
// Created by Happig on 2021/1/24.
//
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;
#define ENDL "\n"
#define lowbit(x) (x & (-x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 2e5 + 10;

struct node {
    int x, idx;

    bool operator<(const node &p) const {
        return x < p.x;
    }
} a[maxn], b[maxn];

bitset<maxn> res, ans;

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x;
        a[i].idx = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].x;
        b[i].idx = i;
    }
    sort(a, a + n);
    sort(b, b + m);
    res.set(), ans.set();
    int pos = 0;
    for (int i = 0; i < m; i++) {
        while (pos < n && a[pos].x < b[i].x) {
            res.reset(a[pos].idx);
            pos++;
        }
        ans &= (res >> b[i].idx);
    }
    int sum = 0;
    for (int i = 0; i <= n - m; i++) {
        if (ans[i]) sum++;
    }
    cout << sum << endl;
    return 0;
}