RenaMoe's Blog

念念不忘，必有回响

0%

题解 P3527 [POI2011]MET-Meteors

发表于 更新于 分类于 ， Valine：

有 n 个成员国。环形轨道被分为 m 份（第 m份和第 1 份相邻），第 i 份上有第 \(a_i\) 个国家的太空站。有 k 场陨石雨，[l, r]的轨道区间加上 a。

第 i 个成员国希望能够收集 \(p_i\) 单位的陨石样本。判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

\(n,m,k\le 3\times 10^5\)

思路

这类题可以想到用整体二分来解决。

\(O(nlog^2n)\) 做法

将 k 场陨石雨作为修改，n 个国家作为查询。

二分答案时间 mid，mid 之前的修改放左边，之后的修改放右边；mid 之前收集足够的国家放左边，否则放右边。

将陨石雨以差分形式修改，利用树状数组 \(O(logn)\) 查询每段轨道在某一时间的陨石数，这样每个国家暴力查总陨石数，即可划分国家。

这样分治下去复杂度 \(O(nlog^2n)\)，能过这道题

\(O(nlogn)\) 做法

感谢 jly 神仙的题解 启发，这个思路太棒了。

同样是二分答案时间 mid，陨石雨作为询问（修改），但是要把 m 个轨道放进去和修改一块二分。

mid 之前的询问放左边，之后的放右边；mid 之前轨道所在国家收集足够的放左边，否则放右边。

二分之前将所有询问按位置排序，分治时可以通过 two-pointers 扫描轨道和询问，从而计算每个轨道的陨石数，每个点的查询 \(O(1)\)，分治每层 \(O(n)\)，成功降了一个 log。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

namespace RenaMoe {

template<typename T> inline void read(T &x) {}
template<typename TT> inline void print(TT x, char end = '\n') {}

typedef long long LL;

const int N = 5e5 + 9;

struct Ask {
    int pos, id;
    LL a;
    Ask() {}
    Ask(int _p, int _i, LL _a) {
        pos = _p, id = _i, a = _a;
    }
    inline bool operator <(const Ask &t) const {
        return pos < t.pos;
    }
};

int n, m, cnt;
int o[N], p[N], s[N], s1[N], s2[N], ans[N];
LL sum[N];
Ask q[N<<1], q1[N<<1], q2[N<<1];

// l,r答案时间；sl,sr轨道区间；ql,qr询问区间
void solve(int l, int r, int sl, int sr, int ql, int qr) {
    if (sl > sr || ql > qr) return;
    for (int i = sl; i <= sr; ++i) sum[o[s[i]]] = 0;
    if (l == r) {
        LL qsum = 0;
        for (int i = sl, j = ql; i <= sr; ++i) {
            while (j <= qr && q[j].pos <= s[i])
                qsum += q[j].a, j++;
            if (sum[o[s[i]]] < p[o[s[i]]])
                sum[o[s[i]]] += qsum;
        }
        for (int i = sl; i <= sr; ++i) {
            if (sum[o[s[i]]] >= p[o[s[i]]])
                ans[o[s[i]]] = l;
            else ans[o[s[i]]] = -1;
        }
        return;
    }

    int mid = (l + r) >> 1, cq1 = 0, cq2 = 0;
    for (int i = ql; i <= qr; ++i) {
        if (q[i].id <= mid) q1[++cq1] = q[i];
        else q2[++cq2] = q[i];
    }
    for (int i = 1; i <= cq1; ++i) q[ql+i-1] = q1[i];
    for (int i = 1; i <= cq2; ++i) q[ql+cq1+i-1] = q2[i];

    LL qsum = 0;
    for (int i = sl, j = ql; i <= sr; ++i) {
        while (j < ql+cq1 && q[j].pos <= s[i])
            qsum += q[j].a, j++;
        if (sum[o[s[i]]] < p[o[s[i]]])
            sum[o[s[i]]] += qsum;
    }
    int cs1 = 0, cs2 = 0;
    for (int i = sl; i <= sr; ++i) {
        if (sum[o[s[i]]] >= p[o[s[i]]])
            s1[++cs1] = s[i];
        else s2[++cs2] = s[i];
    }
    for (int i = 1; i <= cs1; ++i) s[sl+i-1] = s1[i];
    for (int i = 1; i <= cs2; ++i) s[sl+cs1+i-1] = s2[i];
    for (int i = sl+cs1; i <= sr; ++i)
        p[o[s[i]]] -= sum[o[s[i]]], sum[o[s[i]]] = 0;

    solve(l, mid, sl, sl+cs1-1, ql, ql+cq1-1);
    solve(mid+1, r, sl+cs1, sr, ql+cq1, qr);
}

inline void main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i) read(o[i]);
    for (int i = 1; i <= n; ++i) read(p[i]);
    for (int i = 1; i <= m; ++i) s[i] = i;
    for (int i = 1; i <= n; ++i) ans[i] = -1;
    int k, l, r;
    LL a;
    read(k);
    for (int i = 1; i <= k; ++i) {
        read(l), read(r), read(a);
        if (l <= r) {
            q[++cnt] = Ask(l, i, a);
            if (r < m) q[++cnt] = Ask(r+1, i, -a);
        }
        else {
            q[++cnt] = Ask(1, i, a);
            if (l > r + 1) {
                q[++cnt] = Ask(r+1, i, -a);
                q[++cnt] = Ask(l, i, a);
            }
        }
    }
    sort(q+1, q+cnt+1);
    solve(1, k, 1, m, 1, cnt);
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == -1) puts("NIE");
        else print(ans[i]);
    }
}
}

int main() {
    RenaMoe::main();
    return 0;
}

真的跑的飞快 >_<

jly 题解讲的不是很详细，我太菜了根本看不懂，这道题我做了一晚上+一早上qwq

空间要开 3 倍以上啊啊啊，只开了 2 倍的我 wa 了几个小时！