AK-dream

Siano[BZOJ4293]

AK-dream

发布于：2020年3月25日
次浏览

【题目描述】
农夫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;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/16e80e56.html/

更新于：2020年9月7日

线段树

评论