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

• 2018-02-10
• 0
• 0

## 输入输出样例

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

6
6
18
0

## Solution:

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

## 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;
}


#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai