题解：CF338E Optimize!

· · 题解

一种不基于值域的做法，不知道和 hall 定理有啥关系。

我们需要 A_i+B_i\ge H\Rightarrow A_i\ge H-B_i，把所有的 B_i\leftarrow H-B_i，直接就转化为判断对于每一个长度为 len 的 A 的连续子序列里面排两者都排序之后是不是 \forall i\in [1,M],A_i\ge B_i。

考虑把 B 排序，二分出 A 的合法区间，相当于我们需要实时判断 \forall i\in [1, N], pre_i \le i，对于 pre_i 的修改是单点的。

发现这个东西没那么好维护，因为是单点的修改，所以把每一个点的贡献覆盖上去（区间 +1）就可以了（其实这里区间覆盖也是可以的，就是序列上覆盖一段然后另一段加等差数列），我们只需要维护区间 add，全局 min 的线段树即可。

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {x = min(x, c);}
void chmax(int &x, int c) {x = max(x, c);}

const int maxn = 15e4 + 10, mod = 998244353;
int N, M, K;
int A[maxn], B[maxn], pos[maxn];
namespace segt {
int mn[maxn << 1], tag[maxn << 1];
void pushdown (int u) {
    if (tag[u]) {
        mn[u << 1] += tag[u]; tag[u << 1] += tag[u];
        mn[u << 1 | 1] += tag[u]; tag[u << 1 | 1] += tag[u];
        tag[u] = 0;
    }
}
void pushup (int u) {
    mn[u] = min (mn[u << 1], mn[u << 1 | 1]);
}
void build (int u, int l, int r) {
    if (l == r) {
        mn[u] = -(M - l + 1); tag[u] = 0; return;
    }
    int mid = (l + r) >> 1;
    build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r), pushup (u); 
}
void upd (int u, int l, int r, int ql, int qr, int x) {
    if (ql > qr) return;
    if (ql <= l && qr >= r) {
        mn[u] += x; tag[u] += x;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown (u);
    if (ql <= mid) upd (u << 1, l, mid, ql, qr, x);
    if (qr > mid) upd (u << 1 | 1, mid + 1, r, ql, qr, x);
    pushup (u); 
}
}

void solve() {
    cin >> N >> M >> K;
    L (i, 1, M) cin >> B[i], B[i] = K - B[i];
    L (i, 1, N) cin >> A[i];
    sort (B + 1, B + 1 + M);
    L (i, 1, N) {
        int l = 0, r = M, res = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            (A[i] >= B[mid] ? res = mid, l = mid + 1 : r = mid - 1);
        }
        pos[i] = res;
    }
    segt::build (1, 1, M);
    int res = 0;
    L (i, 1, N) {
        segt::upd (1, 1, M, 1, pos[i], 1);
        if (i >= M) {
            res += segt::mn[1] >= 0;
            segt::upd (1, 1, M, 1, pos[i - M + 1], -1);
        }
    }
    cout << res << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--)solve();
  return 0;
}