【题目描述】
农夫Byteasar买了一片$n$亩的土地,他要在这上面种草。

他在每一亩土地上都种植了一种独一无二的草,其中,第$i$亩土地的草每天会长高$a[i]$厘米。

Byteasar一共会进行$m$次收割,其中第$i$次收割在第$d[i]$天,并把所有高度大于等于$b[i]$的部分全部割去。Byteasar想知道,每次收割得到的草的高度总和是多少,你能帮帮他吗?

【输入格式】
第一行包含两个正整数$n,m(1\leq n,m\leq 500000)$,分别表示亩数和收割次数。

第二行包含$n$个正整数,其中第$i$个数为$a[i]$,依次表示每亩种植的草的生长能力。

接下来$m$行,每行包含两个正整数$d[i],b[i]$,依次描述每次收割。

数据保证$d[1]<d[2]<…<d[m]$,并且任何时刻没有任何一亩草的高度超过$10^{12}$。

【输出格式】
输出$m$行,每行一个整数,依次回答每次收割能得到的草的高度总和。

我们发现 如果$a[i]\ge a[j]$那么任一时刻 第$i$亩草的高度都一定大于等于第$j$亩草

并不难证明吧 如果没有收割 那么结论显然成立 如果有收割 那要么是第$i$亩草和第$j$亩草都被割成$b$了 要么是第$i$亩草被割成$b$了 第$j$亩草还没长到$b$

所以我们把$n$亩草按生长速度从小到大排序 由于此时草的高度在任一时刻都是单调递增的 那么每次割草都一定是一段后缀能被收割

既然每次都是连续的一段被收割 我们就可以用线段树来维护这个东西

首先看看我们需要用线段树进行哪些操作

  1. 由于要查询割去的高度和 而割去的高度和就等于总高度和-区间长度$\times b$所以肯定要支持查询区间和 但是草的长度每天都在更新 不可能一天一天地更新 所以我们对于每个区间记录两个值$day$表示该区间从第$day$天开始就再没有草被割过了(就是最后一次有草被割的天数+1)$sum$表示第$day$天开始前草的总高度$spd$表示区间内草生长速度的总和 那么我们查询第$k$天区间草的高度和 就是$sum+(k-day+1)*spd$

  2. 有区间修改(把$i\sim n$区间内的草全部割成$b$) 要维护两个懒标记$tagd$和$tagb$

  3. 查询每次割草割的是从哪里开始的后缀需要在线段树上二分 所以我们多维护一循区间左端点那一亩草的$day,sum,spd$,这样方便进行二分

其实代码也没有很长。。。具体细节在代码中有注释

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T> void read(T &x) {
x = 0; T f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
x *= f;
}

int n, m;
ll a[500005], ans;

struct segtree{
struct tree{
int l, r;
ll sum, spd, day, mn, mnspd;
ll tagd, tagb;
} tr[2000005];

#define lson ind<<1
#define rson ind<<1|1

inline void pushup(int ind) {
tr[ind].day = tr[rson].day;
//每次修改的是一段后缀 所以右儿子的day肯定大于等于左儿子
tr[ind].spd = tr[lson].spd + tr[rson].spd;
//其实不用每次都更新 因为懒得改了
tr[ind].mnspd = tr[lson].mnspd;
//这个也不用更新。。。
tr[ind].sum = tr[lson].sum + (tr[ind].day - tr[lson].day) * tr[lson].spd + tr[rson].sum + (tr[ind].day - tr[rson].day) * tr[rson].spd;
//当前节点的sum等于左儿子和右儿子在第day-1天的草长度和 代到我文章上面那个算第k天草长度的式子里就是这个
tr[ind].mn = tr[lson].mn + (tr[rson].day - tr[lson].day) * tr[lson].mnspd;
//单独维护一下左端点
}

inline void add(int ind, ll d, ll b) {
tr[ind].day = d + 1; //第d天被割了 所以day=d+1
tr[ind].sum = 1ll * (tr[ind].r - tr[ind].l + 1) * b; //全部草长度变为b
tr[ind].mn = b;
tr[ind].tagd = d;
tr[ind].tagb = b;
}

inline void pushdown(int ind) {
if (!tr[ind].tagd) return;
add(lson, tr[ind].tagd, tr[ind].tagb);
add(rson, tr[ind].tagd, tr[ind].tagb);
tr[ind].tagd = tr[ind].tagb = 0;
}

void build(int ind, int l, int r) {
tr[ind].l = l, tr[ind].r = r, tr[ind].sum = tr[ind].mn = 0, tr[ind].day = 1;
if (l == r) {
tr[ind].spd = a[l];
tr[ind].mnspd = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid); build(rson, mid + 1, r);
pushup(ind);
}

int find(int ind, ll d, ll b) {
int l = tr[ind].l, r = tr[ind].r;
if (l == r) {
if (tr[ind].mn + (d - tr[ind].day + 1) * tr[ind].mnspd > b) return l;
else return l + 1;
}
pushdown(ind);
if (tr[rson].mn + (d - tr[rson].day + 1) * tr[rson].mnspd > b) return find(lson, d, b);
else return find(rson, d, b);
}

ll query(int ind, int x, int y, ll d, ll b) {
if (x > y) return 0ll;
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
return tr[ind].sum + (d - tr[ind].day + 1) * tr[ind].spd - 1ll * (r - l + 1) * b;
}
pushdown(ind);
int mid = (l + r) >> 1;
ll ret = 0;
if (x <= mid) ret += query(lson, x, y, d, b);
if (mid < y) ret += query(rson, x, y, d, b);
return ret;
}

void update(int ind, int x, int y, ll d, ll b) {
if (x > y) return;
int l = tr[ind].l, r = tr[ind].r;
if (x <= l && r <= y) {
add(ind, d, b);
return;
}
pushdown(ind);
int mid = (l + r) >> 1;
if (x <= mid) update(lson, x, y, d, b);
if (mid < y) update(rson, x, y, d, b);
pushup(ind);
}
} T;

int main() {
read(n); read(m);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
sort(a + 1, a + n + 1);
T.build(1, 1, n);
for (int i = 1; i <= m; i++) {
ll d, b;
read(d); read(b);
int st = T.find(1, d, b);
ans = T.query(1, st, n, d, b);
printf("%lld\n", ans);
T.update(1, st, n, d, b);
}
return 0;
}

评论