专栏文章

P3527 题解

rrainygame
P3527题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqd7p04
此快照首次捕获于
2025/12/04 02:53
3 个月前
此快照最后确认于
2025/12/04 02:53
3 个月前
查看原文
来一篇 O(nlog⁡n)O(n\log n) 的题解！
答案具有可二分性，考虑整体二分。设当前分治区间为 [l,r][l,r]，任务是判断 QQ 集合内的国家答案是否小于等于 m=l+r2m=\dfrac{l+r}{2}。
O(nlog⁡2n)O(n\log^2n) 的做法比较简单：将 [l,m][l,m] 的操作都执行一次，然后再对于 QQ 国家集合内的太空站都单点求值后加起来判断，可以用 BIT 维护这个操作。最后二分到两个区间时，(m,r](m,r] 的国家目标需要调整，使得 [l,m][l,m] 的操作不会影响到它们。
还有一个更加暴力的做法：将 [l,m][l,m] 操作转化成差分数组上的单点加，然后扫一遍整个序列，也可以求出每个太空站的值。这个做法是可以优化的，因为“关键点”个数只有 O(∑i∈Q∣Si∣+r−l)O(\sum\limits_{i\in Q}\lvert S_i\rvert+r-l)（其中 SiS_i 表示属于国家 ii 的空间站集合），所以如果这些点排好序了，那么就可以直接扫一遍，复杂度优化为 O(nlog⁡n)O(n\log n)！
考虑在第一次分治之前就排好序，那么在后面的分治中，可以将点集有序地分为两部分，复杂度不会退化。
注意事项：
  • 计算过程中可能会爆 long long。
  • 注意有些国家可能没有空间站。
比两只 log⁡\log 好写的代码：
CPP
#include <bits/stdc++.h>
using namespace std;
typedef __int128 _int;
#define MAXN 300005

int n, m, q; int a[MAXN], p[MAXN], ans[MAXN]; _int tp[MAXN];
struct Node{int x, k, id;}; vector<Node> Q;

void sol(int l, int r, vector<Node> Q){
    if (l == r){for (auto i: Q) if (!i.k) ans[a[i.x]]=l; return;} int mid((l+r)>>1);
    for (_int i(0), res(0); i<Q.size(); ++i){
        if (!Q[i].k) tp[a[Q[i].x]] += res; else if (Q[i].id <= mid) res += Q[i].k;
    }
    vector<Node> ql, qr;
    for (auto i: Q){
        if (i.k) (i.id <= mid ? ql : qr).push_back(i);
        else if (tp[a[i.x]] >= p[a[i.x]]) ql.push_back(i);
        else p[a[i.x]] -= tp[a[i.x]], tp[a[i.x]] = 0, qr.push_back(i);
    }
    for (auto i: Q) tp[a[i.x]] = 0; sol(l, mid, ql); sol(mid+1, r, qr);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> m >> n; for (int i(1); i<=n; ++i) cin >> a[i], Q.push_back({i, 0, 0});
    for (int i(1); i<=m; ++i) cin >> p[i]; cin >> q;
    for (int i(1), l, r, k; i<=q; ++i){
        cin >> l >> r >> k;
        if (l <= r) Q.push_back({l, k, i}), Q.push_back({r+1, -k, i});
        else Q.push_back({1, k, i}), Q.push_back({r+1, -k, i}), Q.push_back({l, k, i});
    }
    sort(Q.begin(), Q.end(), [](Node a, Node b){return a.x == b.x ? !a.k < !b.k : a.x < b.x;});
    memset(ans, 0x3f, sizeof(ans)); sol(1, q+1, Q);
    for (int i(1); i<=m; ++i) if (ans[i] > q) cout << "NIE\n"; else cout << ans[i] << '\n';

    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...