JZTXT

离线算法

发布时间 2024-01-07 01:22:54作者: wangxuzhou

莫队

模板题

考虑一种暴力，维护 \(cnt_i\) 表示 \(i\) 当前出现了多少次。

对于所有询问 \(i\) 保存询问 \(i-1\) 的 \(cnt\)，暴力删除上一次询问有，这一次没有的数，并加入上一次询问没有，这一次询问有的数。

加入、删除一个数的代码 
void add(int x) {
    cnt[x]++;

    if (cnt[x] == 1)
        ans++;
}
void del(int x) {
    cnt[x]--;

    if (!cnt[x])
        ans--;
}
查询代码 
while (l > ql)
    add(a[--l]);

while (r < qr)
    add(a[++r]);

while (l < ql)
    del(a[l++]);

while (r > qr)
    del(a[r--]);

cout << ans << '\n';

利用分块的思想对上述算法进行优化。

把询问离线下来，并对整个序列分块，左端点在同一个块的一起处理，左端点所在块相同的询问在按右端点从小到大处理。

这样，左端点最多移动 \(m\sqrt{n}\) 次，右端点最多移动 \(m\sqrt{n}\) 次，总时间复杂度为 \(m\sqrt{n}\)。

#include <bits/stdc++.h>
using namespace std;
int n, m, L, now, a[100005], b[100005], cnt[100005], ans[100005];
struct query {
    int l, r, id;
} q[100005];
bool cmp(query x, query y) {
    if (b[x.l] == b[y.l])
        return x.r < y.r;

    return b[x.l] < b[y.l];
}
void add(int x) {
    cnt[x]++;

    if (cnt[x] == 1)
        now++;
}
void del(int x) {
    cnt[x]--;

    if (!cnt[x])
        now--;
}
int main() {
    cin >> n;
    L = sqrt(n);

    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = (i - 1) / L + 1;

    cin >> m;

    for (int i = 1; i <= m; i++)
        cin >> q[i].l >> q[i].r, q[i].id = i;

    sort(q + 1, q + m + 1, cmp);

    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (l > q[i].l)
            add(a[--l]);

        while (r < q[i].r)
            add(a[++r]);

        while (l < q[i].l)
            del(a[l++]);

        while (r > q[i].r)
            del(a[r--]);

        ans[q[i].id] = now;
    }

    for (int i = 1; i <= m; i++)
        cout << ans[i] << '\n';

    return 0;
}

整体二分

对于一些有多次询问，且答案具有单调性的题目，对于单个询问二分复杂度为 \(O(n\log v)\)，总时间复杂度达到 \(O(qn\log v)\)，其中 \(v\) 表示答案上限，直接二分不可做。

整体二分的核心思路：枚举答案区间 \([l,r]\)，确定那些询问的答案在 \([l,r]\) 中。

对于每个答案，直接枚举所有询问显然是不可取的。
可以利用分治的思想，先确定答案区间 \([1,v]\)、询问区间 \([1,q]\)，然后考虑将答案区间分为两个长度为 \(\dfrac{v}{2}\) 级别的答案区间 \([1,\dfrac{v}{2}],[\dfrac{v}{2}+1,v]\)，划分时分别确定那些询问在答案区间 \([1,\dfrac{v}{2}],[\dfrac{v}{2}+1,v]\) 中，再将这些答案区间分别划为两半，以此类推。
最后就得到 \(v\) 个长度为 \(1\) 的答案区间，也同时得到了每个答案区间包含了那些询问。

这是整体二分递归时下传的几个参数：

  • \(l,r\) 表示当前考虑的答案区间。

  • \(ql,qr\) 表示答案在 \([l,r]\) 中的询问编号为 \(ql\sim qr\)。（整体二分在划分区间后会重新排列询问顺序）

整体二分代码框架大致如下：

void solve(int l, int r, int ql, int qr) {
    if (l == r) {
        for (int i = ql; i <= qr; i++)
            ans[q[i]] = l;    //答案确定，记录区间

        return;
    }

    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;

    //......

    for (int i = ql; i <= qr; i++) {
        if (/*......*/)
            q1[++cnt1] = q[i];    //确定哪些询问的答案在 [l,mid] 中
        else
            q2[++cnt2] = q[i];    //确定哪些询问的答案在 [mid+1,r] 中
    }

    for (int i = ql; i <= ql + cnt1 - 1; i++)
        q[i] = q1[i - ql + 1];    //将答案小的放在前面，以便往下递归时快速找到查询区间

    for (int i = ql + cnt1; i <= qr; i++)
        q[i] = q2[i - ql - cnt1 + 1];

    solve(l, mid, ql, ql + cnt1 - 1);    //继续划分答案区间
    solve(mid + 1, r, ql + cnt1, qr);
}

思路

例题

[POI2011] MET-Meteors

题目给定的是一个环，第一步肯定是断环成链，将 \(o_i\) 复制一份到 \(o_{i+m}\)。

显然，答案具有单调性，对于每个国家二分一次的做法复杂度不能接受，考虑整体二分。

考虑快速区分某个询问的答案是在 \([l,mid]\) 还是 \([mid+1,r]\)。
对于一次划分操作，直接执行一遍 \(l\sim mid\) 操作，用差分树状数组维护每个下标的值。
对于国家 \(i\)，如果它在操作完之后总共收集到的陨石达到 \(p_i\)，那么它的答案在 \([l,mid]\)，否则在 \([mid+1,r]\)。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
int n, m, k, o[1000005], q[1000005], q1[1000005], q2[1000005];
long long c[1000005], p[1000005], ans[1000005];
vector<int> s[1000005];
struct data {
    int l, r;
    long long a;
} d[1000005];
void add(int x, int k) {
    while (x <= m) {
        c[x] += k;
        x += (x & -x);
    }
}
long long query(int x) {
    long long ret = 0;

    while (x) {
        ret += c[x];
        x -= (x & -x);
    }

    return ret;
}
long long sum(int x) {
    long long ret = 0;

    for (auto i : s[x]) {
        ret += query(i);

        if (ret > p[x])
            return ret;
    }

    return ret;
}
void solve(int l, int r, int ql, int qr) {
    if (l == r) {
        for (int i = ql; i <= qr; i++)
            ans[q[i]] = l;

        return;
    }

    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;

    for (int i = l; i <= mid; i++)
        add(d[i].l, d[i].a), add(d[i].r + 1, -d[i].a);

    for (int i = ql; i <= qr; i++) {
        long long tmp = sum(q[i]);

        if (tmp >= p[q[i]])
            q1[++cnt1] = q[i];
        else
            q2[++cnt2] = q[i], p[q[i]] -= tmp;
            //下面会复原 l~mid 的操作，在后续递归中 p[q[i]] 会少算 sum(q[i])，因为后续计算只在乎大小，可以直接把它减去 sum(q[i])
    }

    for (int i = l; i <= mid; i++)    //复原 l~mid 的操作
        add(d[i].l, -d[i].a), add(d[i].r + 1, d[i].a);

    for (int i = ql; i <= ql + cnt1 - 1; i++)
        q[i] = q1[i - ql + 1];

    for (int i = ql + cnt1; i <= qr; i++)
        q[i] = q2[i - ql - cnt1 + 1];

    solve(l, mid, ql, ql + cnt1 - 1);
    solve(mid + 1, r, ql + cnt1, qr);
}
int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> o[i];
        o[i + m] = o[i];    //破环为链
        s[o[i]].push_back(i);
        s[o[i]].push_back(i + m);
    }

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    cin >> k;

    for (int i = 1; i <= k; i++) {
        cin >> d[i].l >> d[i].r >> d[i].a;

        if (d[i].l > d[i].r)
            d[i].r += m;
    }

    for (int i = 1; i <= n; i++)
        q[i] = i;

    d[++k] = {1, k, (long long)1e18}, m *= 2;
    //这里还要补上一个一定能使任意国家最终收获 p[i] 陨石的操作，用于判断无解，防止溢出
    solve(1, k, 1, n);

    for (int i = 1; i <= n; i++) {
        if (ans[i] == k)
            cout << "NIE\n";
        else
            cout << ans[i] << '\n';
    }

    return 0;
}