[洛谷春令营 D1T2] 割草【线段树】

  • 2018-02-10
  • 0
  • 0

Problem:

题目描述

你有一片 n 亩的土地,在这上面种草。

每一亩土地上都种植了一种独一无二的草,其中,第 亩土地的草每天会长高 厘米。

你一共会进行 m 次收割,其中第 次收割在第 天,并把所有高度大于等于  的部分全部割去。

请回答每次收割得到的草的高度总和是多少。

输入输出格式

输入格式:

第一行包含两个正整数 ,分别表示亩数和收割次数。

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

接下来 m 行,每行包含两个正整数 ,依次描述每次收割。

数据保证 ,并且任何时刻没有任何一亩草的高度超过 

输出格式:

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

输入输出样例

输入样例#1:

4 4
1 2 4 3
1 1
2 2
3 0
4 4

输出样例#1:

6
6
18
0

说明

第1天,草的高度分别为1,2,4,3,收割后变为1,1,1,1。

第2天,草的高度分别为2,3,5,4,收割后变为2,2,2,2。

第3天,草的高度分别为3,4,6,5,收割后变为0,0,0,0。

第4天,草的高度分别为1,2,4,3,收割后变为1,2,4,3。

Solution:

考察线段树维护的毒瘤题。

我们将 a[] 排序,可以发现修改过程中高度保持单调递增

需要支持以下操作:

  1. 将区间 [l, r] 置为 v(收割)
  2. 对于 ∀ i ∈ [l, r],将下标 i 处增加 v * ai(生长)
  3. 查找区间 [1, n] 中第一个比 v 大的数(寻找开始割的位置)
  4. 询问区间 [l, r] 的和(计算收割的草量)

所以相对应地我们要维护:

  1. 延迟标记 settag
  2. 延迟标记 daytag (只存储上述 v 值,在标记下推时再 *ai )
  3. 区间最大值 mx,由于序列单调递增,只需 mx = rc->mx 即可,查询时据此寻找路径
  4. 并不需要维护什么 QAQ

维护是一定要小心,并且注意给出的 b可能大于所有草的高度,需要特判 continue !!!

Code: O(mlogn) [116496KB, 312MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 500005
using namespace std;
typedef long long ll;

template<typename T>
inline void getint(T &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, m;
ll a[MAXN], sum[MAXN], d, b, prev_d;

struct Node{
	ll val, mx, daytag, settag;
	Node *lc, *rc;
	
	Node(): daytag(0), settag(-1), lc(NULL), rc(NULL) {}
	
	inline void update() {val = lc->val + rc->val, mx = rc->mx;}
	// The max value is the most right one, because the heights are increasing
	
	inline void pushdown(int l, int r){
		int smid = l + r >> 1;
		if(settag != -1){
			lc->val = settag * (smid - l + 1), lc->mx = lc->settag = settag, lc->daytag = 0;
			rc->val = settag * (r - smid), rc->mx = rc->settag = settag, rc->daytag = 0;
			settag = -1;
		}
		if(daytag){
			lc->val += (sum[smid] - sum[l - 1]) * daytag, lc->mx += a[smid] * daytag, lc->daytag += daytag;
			rc->val += (sum[r] - sum[smid]) * daytag, rc->mx += a[r] * daytag, rc->daytag += daytag;
			daytag = 0;
		}
	}
} pool[MAXN << 2];

inline Node* newNode(){
	static int topp = 0;
	return &pool[topp++];
}

inline Node* build(int l, int r){
	Node *cur = newNode();
	if(l == r) cur->mx = cur->val = 0;
	else{
		int smid = l + r >> 1;
		cur->lc = build(l, smid);
		cur->rc = build(smid + 1, r);
		cur->update();
	}
	return cur;
}

inline void set(Node *cur, int l, int r, int sl, int sr, ll v){
	if(l == sl && r == sr){
		cur->val = v * (r - l + 1), cur->mx = cur->settag = v, cur->daytag = 0;
		return;
	}
	cur->pushdown(l, r);
	int smid = l + r >> 1;
	if(sr <= smid) set(cur->lc, l, smid, sl, sr, v);
	else if(sl > smid) set(cur->rc, smid + 1, r, sl, sr, v);
	else set(cur->lc, l, smid, sl, smid, v), set(cur->rc, smid + 1, r, smid + 1, sr, v);
	cur->update();
}

inline ll query(Node *cur, int l, int r, int ql, int qr){
	if(l == ql && r == qr) return cur->val;
	cur->pushdown(l, r);
	int smid = l + r >> 1;
	if(qr <= smid) return query(cur->lc, l, smid, ql, qr);
	else if(ql > smid) return query(cur->rc, smid + 1, r, ql, qr);
	else return query(cur->lc, l, smid, ql, smid) + query(cur->rc, smid + 1, r, smid + 1, qr);
}

inline int findpos(Node *cur, int l, int r, ll v){
	if(l == r) return l;
	cur->pushdown(l, r);
	int smid = l + r >> 1;
	if(cur->lc->mx > v) return findpos(cur->lc, l, smid, v);
	else if(cur->rc->mx > v) return findpos(cur->rc, smid + 1, r, v);
	else return -1;
}

int main(){
	getint(n), getint(m);
	for(register int i = 1; i <= n; i++) getint(a[i]);
	sort(a + 1, a + n + 1);
	for(register int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
	Node *root = build(1, n);
	for(register int i = 1; i <= m; i++){
		prev_d = d, getint(d), getint(b);
		root->val += sum[n] * (d - prev_d), root->mx += a[n] * (d - prev_d), root->daytag += d - prev_d;
		int p = findpos(root, 1, n, b);
		if(p == -1) puts("0");  // Beware that the b[i] may be too big
		else{
			ll cutgrass = query(root, 1, n, p, n) - (n - p + 1) * b;
			printf("%lld\n", cutgrass);
			set(root, 1, n, p, n, b);
		}
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai