Description
农夫Byteasar买了一片n亩的土地，他要在这上面种草。他在每一亩土地上都种植了一种独一无二的草，其中，第i亩土地的草每天会长高(a_i)厘米。Byteasar一共会进行(m)次收割，其中第i次收割在第(d_i)天，并把所有高度大于等于(b_i)的部分全部割去。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
Hint
样例解释
- 第 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。
对于100的数据，(1≤n,m≤5×10^5，1≤a_i≤10^6，1≤d_i,b_i≤10^{12})。
数据保证(d_1<d_2<...<d_m)，并且任何时刻没有任何一亩草的高度超过(10^{12})。
（来源：bzoj4293）
Solution
这是一道思维较简单，代码实现难的题目。线段树向我发起了挑衅......
- 我们首先应该明白，对于生长速度已经确定的几种草，他们的高度应该具有与生长速度一样的单调性。
- 那么我们先排一下序，所以我们每次割草时，只需要求这个数组后面一段草的割下来的高度和。高度和可以用（总高度-限制的高度×该段草的数量）得到。
- 所以我们需要维护一些东西，去求割草的起始位置，割草时某一个区间（也就是割草起始位置到最后）草的总高度。
- 这些东西是什么呢，在代码中我有解释了。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define int long long
#define L rt<<1
#define R rt<<1|1
using namespace std;
const int maxn=5e5+5;
template<typename T> void rd(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 ^ 48);
x *= f;
}
int n,m,a[maxn],t[maxn<<2],bgt[maxn<<2],spd[maxn<<2],mspd[maxn<<2],mn[maxn<<2],lazyd[maxn<<2],lazyb[maxn<<2];
//bgt->开始重新生长的时间（begin time）spd->生长速度(speed) mspd->区间最小生长速度(min speed)用于求割草的起点 mn->区间最矮高度(min) 用于求割草的起点
int ans;
void P(int rt){//常规操作push up
bgt[rt]=bgt[R];
t[rt]=t[L]+(bgt[rt]-bgt[L])*spd[L]+t[R];
mn[rt]=mn[L]+(bgt[R]-bgt[L])*mspd[L];
spd[rt]=spd[L]+spd[R];
mspd[rt]=mspd[L];
}
void U(int rt,int l,int r,int d,int b){//常规操作update，push down中调用
bgt[rt]=d+1;
t[rt]=(r-l+1)*b;
mn[rt]=b;
lazyd[rt]=d;
lazyb[rt]=b;
}
void Pd(int rt,int l,int r){//常规操作 push down
if(!lazyd[rt])return;
int mid=(l+r)>>1;
U(L,l,mid,lazyd[rt],lazyb[rt]);
U(R,mid+1,r,lazyd[rt],lazyb[rt]);
lazyd[rt]=lazyb[rt]=0;
}
void B(int rt,int l,int r){//常规操作build
t[rt]=mn[rt]=0;
bgt[rt]=1;
if(l==r){
spd[rt]=mspd[rt]=a[l];
return;
}
int mid=(l+r)>>1;
B(L,l,mid);
B(R,mid+1,r);
P(rt);
}
int F(int rt,int l,int r,int d,int b){//find找割草起点
if(l==r){
if(mn[rt]+(d-bgt[rt]+1)*mspd[rt]>b)return l;
else return l+1;
}
Pd(rt,l,r);
int mid=(l+r)>>1;
if(mn[R]+(d-bgt[R]+1)*mspd[R]>b)return F(L,l,mid,d,b);
else return F(R,mid+1,r,d,b);
}
int Q(int rt,int l,int r,int x,int y,int d,int b){//常规操作query
if(x>y)return 0LL;
if(x<=l&&r<=y)return t[rt]+(d-bgt[rt]+1)*spd[rt]-(r-l+1)*b;
Pd(rt,l,r);
int mid=(l+r)>>1,ans=0;
if(x<=mid)ans+=Q(L,l,mid,x,y,d,b);
if(y >mid)ans+=Q(R,mid+1,r,x,y,d,b);
return ans;
}
void M(int rt,int l,int r,int x,int y,int d,int b){//常规操作modify
if(x>y)return;
if(x<=l&&r<=y){
U(rt,l,r,d,b);
return;
}
Pd(rt,l,r);
int mid=(l+r)>>1;
if(x<=mid)M(L,l,mid,x,y,d,b);
if(y >mid)M(R,mid+1,r,x,y,d,b);
P(rt);
}
signed main(){
//freopen("1.in","r",stdin);
rd(n);rd(m);
for(int i=1;i<=n;++i)rd(a[i]);
sort(a+1,a+1+n);
B(1,1,n);
for(int i=1,d,b,pos;i<=m;++i){
rd(d),rd(b);
pos=F(1,1,n,d,b);//查询割草的起点
ans=Q(1,1,n,pos,n,d,b);//割完草了，求被割的高度和（常规操作）
printf("%lld
",ans);
M(1,1,n,pos,n,d,b);//割完草了，修改被割的草的高度
}
return 0;
}