P4477 题解

creation_hy · 2023-12-17 23:21:11 · 题解

再水一篇题解

水题。询问形式容易联想到莫队，让 A_i 变为 Z-a_i 后，要求变为 B_i\le A_i。

容易想到容斥。将 A 排序后，设 f_i 表示有多少个 B_i 小于等于 A_i，由于 A_i 单调，答案即为匹配的最大空缺，即 n-\max(i-f_i)。

然后就很简单了，设 pos_i 表示第一个大于等于 B_i 的 A_i，则插入数字相当于把对于 i\in[pos,n] 的 i-f_i 全部减一，删除为全部加一。

用线段树维护就行了。

时间复杂度 O(q\sqrt m \log n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e4 + 5;
const int M = 7e5 + 5;
int n, m, q, lim, a[M], b[N], pos[N], sq, num[N], ans[N];
struct Query
{
    int l, r, id;
    inline bool operator<(const Query &t) const
    {
        return num[l] == num[t.l] ? r < t.r : l < t.l;
    }
} qy[N];
struct SegTree
{
    int tag[M], mx[M];
    inline int ls(int p) { return p << 1; }
    inline int rs(int p) { return p << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[ls(p)], mx[rs(p)]); }
    inline void push_down(int p)
    {
        if (tag[p])
        {
            tag[ls(p)] += tag[p], tag[rs(p)] += tag[p];
            mx[ls(p)] += tag[p], mx[rs(p)] += tag[p];
            tag[p] = 0;
        }
    }
    inline void build(int p, int l, int r)
    {
        if (l == r)
        {
            mx[p] = l;
            return;
        }
        int mid = l + r >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        push_up(p);
    }
    inline void update(int p, int l, int r, int dl, int dr, int k)
    {
        if (dl > dr)
            return;
        if (dl <= l && r <= dr)
        {
            mx[p] += k, tag[p] += k;
            return;
        }
        push_down(p);
        int mid = l + r >> 1;
        if (dl <= mid)
            update(ls(p), l, mid, dl, dr, k);
        if (mid < dr)
            update(rs(p), mid + 1, r, dl, dr, k);
        push_up(p);
    }
} seg;
inline void add(int x) { seg.update(1, 1, n, pos[x], n, -1); }
inline void del(int x) { seg.update(1, 1, n, pos[x], n, 1); }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> lim, sq = sqrt(m);
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] = lim - a[i];
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i], num[i] = (i - 1) / sq + 1;
        pos[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a;
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
        cin >> qy[i].l >> qy[i].r, qy[i].id = i;
    sort(qy + 1, qy + 1 + q);
    seg.build(1, 1, n);
    for (int i = 1, l = 1, r = 0; i <= q; i++)
    {
        while (l > qy[i].l)
            add(--l);
        while (r < qy[i].r)
            add(++r);
        while (l < qy[i].l)
            del(l++);
        while (r > qy[i].r)
            del(r--);
        ans[qy[i].id] = max(0, n - seg.mx[1]);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    return 0;
}