ZROI NOIP十连测 D9T2

发表于 更新于 本文字数： 650 阅读时长 ≈ 2 分钟

纪念我本场唯一一道赛时过的题

题意：有一个长度为 10910^9 的序列 aa，初始均为 00。给定 nn 个序列上的区间 [li,ri][l_i,r_i]。进行 mm 次操作，每次给定 p,xp,x，表示让 apa_p 加上 xx。每次操作之后，令区间 [li,ri][l_i,r_i] 的权值为 ∑j=liriaj\sum\limits_{j=l_i}^{r_i} a_j，你需要找到这 nn 区间中的最大权值。

1≤n,m≤4×1051\leq n,m\leq 4\times 10^5

容易发现如果一个区间被另一个区间包含，那么这个区间的权值一定小于或等于更大的那个区间，也就是说它一定不可能是权值最大的那个。对于这类区间，我们直接忽略。

下面考虑剩下的那部分区间，可以发现若将其按照左端点升序排序，其右端点也一定是升序的，因为如果存在一个区间的右端点比上一个区间的右端点小，那它一定会被上一个区间所包含。

那么对于一次单点修改，我们可以将其转换成对这些区间的区间修改，这个区间的左端点即为 第一个右端点大于等于 pp 的区间的编号，右端点为 最后一个左端点小于等于 pp 的区间的编号。最后在每次修改后查询全局最大值即可。

语言描述可能比较绕，具体见代码。

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
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int maxn = 4e5 + 5;
int n, m;
struct segment_tree
{
    int tree[maxn << 2], tag[maxn << 2];
    void push_up(int p) { tree[p] = max(tree[p * 2], tree[p * 2 + 1]); }
    void push_down(int p, int l, int r)
    {
        tree[p * 2] += tag[p];
        tree[p * 2 + 1] += tag[p];
        tag[p * 2] += tag[p];
        tag[p * 2 + 1] += tag[p];
        tag[p] = 0;
    }
    void add(int p, int l, int r, int nl, int nr, int val)
    {
        if (l >= nl && r <= nr)
        {
            tag[p] += val;
            tree[p] += val;
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) / 2;
        if (mid >= nl)
            add(p * 2, l, mid, nl, nr, val);
        if (mid < nr)
            add(p * 2 + 1, mid + 1, r, nl, nr, val);
        push_up(p);
    }
} T;
struct node
{
    int l, r;
} q[maxn];
int l[maxn], r[maxn], tot;
bool cmp(node x, node y)
{
    if (x.l == y.l)
        return x.r > y.r;
    return x.l < y.l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> q[i].l >> q[i].r;
    sort(q + 1, q + 1 + n, cmp);
    int maxr = 0;
    for (int i = 1; i <= n; i++)
    {
        if (maxr < q[i].r)
        {
            l[++tot] = q[i].l;
            r[tot] = q[i].r;
            maxr = q[i].r;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int p, x;
        cin >> p >> x;
        int nl = lower_bound(r + 1, r + 1 + tot, p) - r;
        int nr = upper_bound(l + 1, l + 1 + tot, p) - l - 1;
        if (nl <= nr)
            T.add(1, 1, tot, nl, nr, x);
        cout << T.tree[1] << endl;
    }
    return 0;
}