整体二分 | POI2011 MET-Meteors 题解

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

洛谷题面

以下认为 n,m,kn,m,k 同阶，时间复杂度都用 nn 表示。

Step 1

先思考一下普通二分的做法。

对于一个国家，设其在第 ww 波陨石雨后能收集到足够的陨石样本。我们设计一个函数 solve(l,r)solve(l,r) 表示答案 ww 在区间 [l,r][l,r] 中，然后取出区间的中间值 midmid ，算出前 midmid 波陨石雨全部下下来所收集到的陨石数量，与希望收集的陨石数量比对，如果收集够了，说明答案 ww 在区间 [l,mid][l,mid] 中，否则，就在区间 (mid,r](mid,r] 中。

我们对于每个国家都进行一遍上述的流程，就可以解决这个问题。但是时间复杂度大概是 O(n2log⁡2n)O(n^2\log^2n) ，显然不可接受。

Step 2：整体二分

由于这些询问不是强制在线的，我们不妨把离线下来，所有询问放在一起二分。

这个过程有点类似于归并排序，相当于我们把所有国家按照收集到足够样本的早晚排序。具体的来说，设第 ii 个国家在第 wiw_i 波陨石雨之后能收集到足够样本，我们以 wiw_i 的数值为关键字，将所有国家升序排序。

我们把所有国家组成一个询问序列。设计一个函数 solve(l,r,x,y)solve(l,r,x,y) ，表示询问序列 [x,y][x,y] 中所有国家的答案 ww 都在区间 [l,r][l,r] 中。我们取出区间 [l,r][l,r] 的中间值 midmid ，算出前 midmid 波陨石雨全部下下来时，询问序列 [x,y][x,y] 中每个国家收集到的陨石数量。对于所有收集够的国家，它们的答案都在区间 [l,mid][l,mid] 中，我们把它们全部放在询问序列 [x,y][x,y] 的左部；对于所有没有收集够的国家，它们的答案都在区间 [mid+1,r][mid+1,r] 中，我们把它们全部放在询问序列 [x,y][x,y] 的右部。这样以来，就可以将这两种情况分开，方便进一步询问。

粗略分析以下时间复杂度，大概是 O(nlog⁡2n)O(n\log^2n)，可以过掉此题。

注意使用树状数组或线段树（常数大，有可能过不了）对左区间进行操作。

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
// 不开 long long 见祖宗
typedef long long ll;
const int maxn = 300005;

struct node
{
    int l, r;
    ll a;
} rain[maxn * 2];
struct node1
{
    // 国家的编号
    int id;
    // 希望收集的陨石数量，即题面中的 p_i
    ll need;
} q[maxn], q1[maxn], q2[maxn];

int n, m, k, o;
vector<int> co[maxn];
int ans[maxn];

// 树状数组
ll tree[maxn * 2];
// 对区间 [p,2*m] 中每个国家的陨石数加上 val
inline void add(int p, ll val)
{
    while (p <= m * 2)
    {
        tree[p] += val;
        p += lowbit(p);
    }
}
// 查询当前国家的陨石数量
inline ll query(int p)
{
    ll sum = 0;
    while (p)
    {
        sum += tree[p];
        p -= lowbit(p);
    }
    return sum;
}

// 整体二分
void solve(int l, int r, int x, int y)
{
    // 二分到终点，区间 [x,y] 的答案都等于二分出的答案
    if (l == r)
    {
        for (int i = x; i <= y; i++)
            ans[q[i].id] = l;
        return;
    }
    int mid = (l + r) / 2, num1 = 0, num2 = 0;
    // 差分思想，将 [l, mid] 的雨全部下下来
    for (int i = l; i <= mid; i++)
        add(rain[i].l, rain[i].a),
            add(rain[i].r + 1, -rain[i].a);
    for (int i = x; i <= y; i++)
    {
        ll sum = 0;
        // 查询，将 [l,mid] 的雨全部下下来后，
        // i 号国家收集到的陨石样本数量

        for (unsigned int j = 0; sum <= q[i].need // 防止爆 long long
                                 && j < co[q[i].id].size();
             j++)
            sum += query(co[q[i].id][j]) + query(co[q[i].id][j] + m);
        // 已经收集够了，放到左边
        if (sum >= q[i].need)
            q1[++num1] = q[i];
        // 还需要收集 q[i].need-sum 个样本，放到右边
        else
            q[i].need -= sum, q2[++num2] = q[i];
    }
    // 清空树状数组
    for (int i = l; i <= mid; i++)
        add(rain[i].l, -rain[i].a),
            add(rain[i].r + 1, rain[i].a);

    // 归并排序，收集够的放在左边，没收集够的放在右边
    for (int i = 1; i <= num1; i++)
        q[x + i - 1] = q1[i];
    for (int i = 1; i <= num2; i++)
        q[x + i + num1 - 1] = q2[i];

    // 继续二分
    solve(l, mid, x, x + num1 - 1);
    solve(mid + 1, r, x + num1, y);
}

int main()
{
    // input
    // 取消同步
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> o;
        // 记录编号为 o 的国家所拥有的轨道
        co[o].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        // 第 i 个国家希望收集的陨石数量
        cin >> q[i].need;
        q[i].id = i;
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
        cin >> rain[i].l >> rain[i].r >> rain[i].a;

    // solve
    // 断环成链
    for (int i = 1; i <= k; i++)
        if (rain[i].l > rain[i].r)
            rain[i].r += m;
    solve(1, k + 1, 1, n);

    // print
    for (int i = 1; i <= n; i++)
    {
        // 第 k 波结束后仍然收集不到，即为第 k+1 波
        if (ans[i] == k + 1)
            cout << "NIE" << endl;
        else
            cout << ans[i] << endl;
    }
    return 0;
}