Description：

$n$ 块土地，一开始都是空的，现在农夫在上面种草，其中第 $i$ 块土地的 草每天会长高 $a_i$ 。农夫还准备进行 $m$ 次收割，第 $j$ 次收割在第 $d_j$ 天， 并会把所有高度大等于 $b_j$ 的部分全部割去。请你求出每次收割得到的草的高度和。

$1\le N \le 5\times 10^5$

Solution：

注意到无论是长高还是收割，操作后数字相对大小不变。将 $a$ 从小到大排序，用线段树维护所有 $a$ 。每次收割的是一段后缀，可以在线段树上二分。

现在考虑怎么维护：首先要记录区间最大值用来二分，还要记录区间和用来询问。但是发现没办法把每天的情况都记录下来，可以在线段树上维护一个一次函数表示在第 $x$ 天草的高度是 $y$ ，初始时 $k=a,b=0$ 。由乘法分配律得 $\begin{align}\sum_{i=1}^n (k_i\times x+b_i)=\sum_{i=1}^nk_i\times x+\sum_{i=1}^n b_i\end{align}$ ，于是区间和也可以直接把 $k$ 和 $b$ 加起来，于是就可以 $O(1)$ 获得所有想询问的值。

于是现在唯一的问题是如何修改，割草相当于让这些草在第 $d_i$ 天高度为 $b_i$ ，于是就可以打一个 $(d_i,b_i)$ 的标记，然后用 $b=b_i-k\times d_i$ 计算出 $b$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

typedef long long ll;

ll a[MAXN];

bool cmp(ll x,ll y){return x > y;}

struct node

{

	int lc,rc;

	ll k,b;ll ks,bs;

	ll tag1,tag2;

	node(){k = b = ks = bs = tag1 = tag2 = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].k = a[l];t[rt].b = 0;

		t[rt].ks = a[l];t[rt].bs = 0;

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].k = t[t[rt].rc].k;

	t[rt].ks = t[t[rt].lc].ks + t[t[rt].rc].ks;

	return;

}

void pushdown(int rt,int l,int r)

{

	if(t[rt].tag1 == 0 && t[rt].tag2 == 0)return;

	t[t[rt].lc].tag1 = t[t[rt].rc].tag1 = t[rt].tag1;

	t[t[rt].lc].tag2 = t[t[rt].rc].tag2 = t[rt].tag2;

	t[t[rt].lc].b = t[rt].tag2 - t[t[rt].lc].k * t[rt].tag1;

	t[t[rt].rc].b = t[rt].tag2 - t[t[rt].rc].k * t[rt].tag1;

	t[t[rt].lc].bs = (mid - l + 1) * t[rt].tag2 - t[t[rt].lc].ks * t[rt].tag1;

	t[t[rt].rc].bs = (r - mid) * t[rt].tag2 - t[t[rt].rc].ks * t[rt].tag1;

	t[rt].tag1 = t[rt].tag2 = 0;

	return;

}

int find(int rt,ll d,ll h,int l,int r)

{

	if(l == r)

	{

		if(h > d * t[rt].k + t[rt].b)--l;

		return l;

	}

	pushdown(rt,l,r);

	if(h < d * t[t[rt].lc].k + t[t[rt].lc].b)return find(t[rt].rc,d,h,mid + 1,r);

	else return find(t[rt].lc,d,h,l,mid);

}

ll query(int rt,int L,int R,ll d,ll h,int l,int r)

{

	if(L > R)return 0;

	if(L <= l && r <= R)

	{

		return t[rt].ks * d + t[rt].bs - (ll)(r - l + 1) * h;

	}

	ll res = 0;

	pushdown(rt,l,r);

	if(L <= mid)res += query(t[rt].lc,L,R,d,h,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,d,h,mid + 1,r);

	return res;

}

void set(int rt,int L,int R,ll d,ll h,int l,int r)

{

	if(L > R)return;

	if(L <= l && r <= R)

	{

		t[rt].tag1 = d;t[rt].tag2 = h;

		t[rt].b = t[rt].tag2 - t[rt].k * t[rt].tag1;

		t[rt].bs = (r - l + 1) * t[rt].tag2 - t[rt].ks * t[rt].tag1;

		return;

	}

	pushdown(rt,l,r);

	if(L <= mid)set(t[rt].lc,L,R,d,h,l,mid);

	if(R > mid)set(t[rt].rc,L,R,d,h,mid + 1,r);

	t[rt].k = t[t[rt].rc].k;

	t[rt].ks = t[t[rt].lc].ks + t[t[rt].rc].ks;

	t[rt].bs = t[t[rt].lc].bs + t[t[rt].rc].bs;

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	sort(a + 1,a + 1 + n,cmp);

	build(root,1,n);

	ll d,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%lld%lld",&d,&b);

		int p = find(root,d,b,1,n);

		printf("%lld\n",query(root,1,p,d,b,1,n));

		set(root,1,p,d,b,1,n);

	}

	return 0;

}