BZOJ4293【PA2015】Siano <线段树>

Problem

【PA2015】Siano

$\mathrm{Time\;Limit:\;30\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

农夫$\mathrm{Byteasar}$买了一片$n$亩的土地，他要在这上面种草。
他在每一亩土地上都种植了一种独一无二的草，其中，第$i$亩土地的草每天会长高$a_i$厘米。
$\mathrm{Byteasar}$一共会进行$m$次收割，其中第$i$次收割在第$d_i$天，并把所有高度大于等于$b_i$的部分全部割去。
$\mathrm{Byteasar}$想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？

Input

第一行包含两个正整数$n,m$，分别表示亩数和收割次数。
第二行包含$n$个正整数，其中第$i$个数为$a_i$，依次表示每亩种植的草的生长能力。
接下来$m$行，每行包含两个正整数$d_i,b_i$，依次描述每次收割。

Output

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

Sample Input

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

Sample Output

6
6
18
0

Explanation

第$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$。

HINT

$1\le n,m\le5\times10^5$, $1\le a_i\le10^6$, $1\le d_i,b_i\le10^{12}$
数据保证$d_1<d_2<\cdots<d_m$，并且任何时刻没有任何一亩草的高度超过$10^12$。

Source

By Claris

标签：线段树

Solution

比较灵活的线段树。

观察题目可以发现一个性质，即长速快的在任意时刻都比长速慢的高度高。这是由于每次修剪都是将所有的剪到同一高度，这样长速快的在修剪后的高度一定大于等于长速慢的在修剪后的高度。

将长速从低到高排序，不会影响询问，并且每次询问剪去的部分一定是一个后缀。那么可以在线段树上分治寻找剪和不剪的分界点，同时累加答案。

对于每个区间需要维护其长速之和、高度和两个基础元素。为了方便询问，需要维护高度的最大和最小值，即该区间最右边和最左边的苗的高度。这样如果当前区间的最大高度$mx\le b$，可知不用继续递归；如果当前区间最小高度$mi\ge b$，可知整个区间都要修剪，打区间标记后返回。而对于标记，每个区间需要维护三个元素$tc,td,ld$，分别表示该区间中的所有高度均变为$tc$，这个变化发生在$td$时刻，上一次递归到该区间的时间是$ld$。询问每次递归进入一个区间先计算从上次递归到该区间也就是$ld$到现在总共长了多少，更新信息。注意$td$和$ld$不能合并为一个变量，这是由于该区间上次被递归到时可能先更新了信息，但是并未打标记，即其下面的子区间没有更新信息，故$td$和$ld$不同。

一棵线段树即可维护，某些细节注意一下即可。

Code

#include <bits/stdc++.h>
#define MAX_N 500000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;    lnt a[MAX_N+5], b, d;
struct node {lnt v, s, tc, td, ld, lv, rv;} tr[MAX_N<<2];
void update(int v) {
    tr[v].v = tr[v<<1].v+tr[v<<1|1].v;
    tr[v].s = tr[v<<1].s+tr[v<<1|1].s;
    tr[v].lv = tr[v<<1].lv, tr[v].rv = tr[v<<1|1].rv;
}
void downtag(int v, int s, int t) {
    if (tr[v].tc == -1) return;
    tr[v<<1].s = tr[v].tc*(mid-s+1);
    tr[v<<1|1].s = tr[v].tc*(t-mid);
    tr[v<<1].lv = tr[v<<1].rv = tr[v].tc;
    tr[v<<1|1].lv = tr[v<<1|1].rv = tr[v].tc;
    tr[v<<1].tc = tr[v<<1|1].tc = tr[v].tc;
    tr[v<<1].td = tr[v<<1|1].td = tr[v].td;
    tr[v<<1].ld = tr[v<<1|1].ld = tr[v].td;
    tr[v].tc = -1;
}
void build(int v, int s, int t) {
    tr[v].tc = -1;	if (s == t) {tr[v].v = a[s]; return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t), update(v);
}
lnt query(int v, int s, int t) {
    lnt ret = 0LL;	tr[v].s += (d-tr[v].ld)*tr[v].v;
    tr[v].lv += a[s]*(d-tr[v].ld), tr[v].rv += a[t]*(d-tr[v].ld);
    if (tr[v].lv >= b) {
        ret = tr[v].s-b*(t-s+1), tr[v].s = b*(t-s+1);
        tr[v].lv = tr[v].rv = tr[v].tc = b, tr[v].td = d;
    } else if (tr[v].rv > b) {
        downtag(v, s, t);
        ret += query(v<<1, s, mid);
        ret += query(v<<1|1, mid+1, t);
        update(v);
    }
    return tr[v].ld = d, ret;
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]);
    sort(a+1, a+n+1), build(1, 1, n);
    while (m--) read(d), read(b), printf("%lld\n", query(1, 1, n));
    return 0;
}