Description

有一个 N 块石头组成的蓄水池,第 i 块石头高度为 ai。你需要进行两种操作: 1.询问蓄水池的容量(蓄水池最多能储存多少水)。 2.将第 x 块石头的高度增加 v。

Hint

1≤N,Q≤1051 \leq N,Q \leq 10^5 1≤ai≤104,1≤x≤N,1≤v≤1041 \leq a_i \leq 10^4, 1\leq x\leq N, 1 \leq v \leq 10^4

Solution

我的做法好像和别人的做法都不太一样。。。 考虑类似于分治的做法，每次求出区间的最大值和最大值所在的位置。然后看这个最大值是否比区间的左右端点高，如果高的话就分开递归求解；否则答案直接加上左右端点较短的那条边所对应的整个矩形大小减去被填上的大小。 然后维护最大值和最大值的位置用一个线段树维护下（单点修改，区间查询），区间被填上的大小（即A[i]的和）再用一个线段树维护下（也是单点修改，区间查询）。算上之前的分治，总复杂度为O(Nlog2N)O(Nlog^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
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int Maxn = 100000 + 100, inf = 0x3f3f3f3f;

int N, M;
int A[Maxn], Sum[Maxn];

namespace SEG1
{
    struct tree
    {
        int Max, sum, pos;
    }Tree[Maxn * 4];

    inline void push_up(int root)
    {
        if (Tree[root << 1].Max >= Tree[root].Max)
            Tree[root].Max = Tree[root << 1].Max, Tree[root].pos = Tree[root << 1].pos;
        if (Tree[root << 1 | 1].Max >= Tree[root].Max)
            Tree[root].Max = Tree[root << 1 | 1].Max, Tree[root].pos = Tree[root << 1 | 1].pos;
    }

    inline void create(int root, int l, int r)
    {
        if (l == r) { Tree[root].sum = Tree[root].Max = A[l]; Tree[root].pos = l; return ; }
        int mid = (l + r) >> 1;
        create(root << 1, l, mid);
        create(root << 1 | 1, mid + 1, r);
        push_up(root);
    }

    inline void update (int root, int l, int r, int x, int y)
    {
        if (l == r)
        {
            Tree[root].sum += y;
            Tree[root].Max = max(Tree[root].Max, Tree[root].sum);
            return ;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update (root << 1, l, mid, x, y);
        else update (root << 1 | 1, mid + 1, r, x, y);
        push_up(root);
    }

    int MAX, POS;
    inline void query (int root, int l, int r, int x, int y)
    {
        if (x > r || y < l) return ;
        if (x <= l && r <= y)
        {
            if (Tree[root].Max >= MAX) MAX = Tree[root].Max, POS = Tree[root].pos;
            return ;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) query (root << 1, l, mid, x, y);
        if (y > mid) query (root << 1 | 1, mid + 1, r, x, y);
    }
}

namespace SEG2
{
    struct node
    {
        int Sum;
    }Tree[Maxn * 4];
    inline void push_up(int root)
    {
        Tree[root].Sum = (Tree[root << 1].Sum + Tree[root << 1 | 1].Sum);
    }
    inline void create(int root, int l, int r)
    {
        if (l == r) { Tree[root].Sum = A[l]; return ; }
        int mid = (l + r) >> 1;
        create(root << 1, l, mid);
        create(root << 1 | 1, mid + 1, r);
        push_up(root);
    }
    inline void update(int root, int l, int r, int x, LL y)
    {
        if (l == r)
        {
            Tree[root].Sum += (y * (r - l + 1));
            return ;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update (root << 1, l, mid, x, y);
        else update (root << 1 | 1, mid + 1, r, x, y);
        push_up(root);
    }

    inline int query (int root, int l, int r, int x, int y)
    {
        if (x > r || y < l) return 0;
        if (x <= l && r <= y) return Tree[root].Sum;
        int mid = (l + r) >> 1, Ans = 0;
        if (x <= mid) Ans += query(root << 1, l, mid, x, y);
        if (y > mid) Ans += query(root << 1 | 1, mid + 1, r, x, y);
        push_up(root);
        return Ans;
    }
}

inline LL Solve (int l, int r)
{
    if (l >= r - 1) return 0;
    SEG1 :: MAX = 0;
    SEG1 :: POS = 0;
    SEG1 :: query (1, 1, N, l + 1, r - 1);
    int pos = SEG1 :: POS;
    if (A[pos] <= A[l] && A[pos] <= A[r])
        return (LL)min(A[l], A[r]) * (r - l - 1) - SEG2 :: query(1, 1, N, l + 1, r - 1);
    return Solve(l, pos) + Solve(pos, r);
}

int main()
{
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    SEG1 :: create(1, 1, N);
    SEG2 :: create(1, 1, N);
    while (M--)
    {
        char S[5];
        scanf("%s", S);
        if (S[0] == 'P')
            printf("%lld\n", Solve(1, N));
        else 
        {
            int x, y;
            scanf("%d%d", &x, &y);
            A[x] += y;
            SEG1 :: update(1, 1, N, x, y);
            SEG2 :: update(1, 1, N, x, y);
        }
    }
    return 0;
}