【BZOJ4293】[PA2015]Siano

Description

农夫Byteasar买了一片n亩的土地，他要在这上面种草。

他在每一亩土地上都种植了一种独一无二的草，其中，第i亩土地的草每天会长高a[i]厘米。

Byteasar一共会进行m次收割，其中第i次收割在第d[i]天，并把所有高度大于等于b[i]的部分全部割去。Byteasar想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？

Input

第一行包含两个正整数n,m(1<=n,m<=500000)，分别表示亩数和收割次数。

第二行包含n个正整数，其中第i个数为a[i](1<=a[i]<=1000000)，依次表示每亩种植的草的生长能力。

接下来m行，每行包含两个正整数d[i],b[i](1<=d[i]<=10^12，0<=b[i]<=10^12)，依次描述每次收割。

数据保证d[1]<d[2]<...<d[m]，并且任何时刻没有任何一亩草的高度超过10^12。

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。

题解：有一个容易发现的性质：长得快的草永远不会比长得慢的草矮。

所以先按ai排序，然后每次只需要二分一个边界，长得比这个边界快的草都会被割掉。然后用线段树维护即可。

但是具体实现不是那么方便，我们的线段树需要维护：带系数的区间加，区间赋值，区间求和，区间求最大值。细节还是看代码吧~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lson x<<1

#define rson x<<1|1

using namespace std;

typedef long long ll;

const int maxn=500010;

int n,m;

ll A[maxn],B,D[maxn],s[maxn<<2],sm[maxn<<2],siz[maxn<<2],ts[maxn<<2],tag[maxn<<2];

void pushup(int x)

{

	s[x]=s[lson]+s[rson],sm[x]=min(sm[lson],sm[rson]);

}

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

{

	int mid=l+r>>1;

	if(~tag[x])

	{

		ts[lson]=ts[rson]=0,tag[lson]=tag[rson]=sm[lson]=sm[rson]=tag[x];

		s[lson]=(mid-l+1)*tag[x],s[rson]=(r-mid)*tag[x];

		tag[x]=-1;

	}

	if(ts[x])

	{

		ts[lson]+=ts[x],ts[rson]+=ts[x];

		s[lson]+=siz[lson]*ts[x],sm[lson]+=A[l]*ts[x],s[rson]+=siz[rson]*ts[x],sm[rson]+=A[mid+1]*ts[x];

		ts[x]=0;

	}

}

void build(int l,int r,int x)

{

	tag[x]=-1;

	if(l==r)

	{

		siz[x]=A[l];

		return ;

	}

	int mid=l+r>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	siz[x]=siz[lson]+siz[rson];

}

ll updata(int l,int r,int x,int a,int b,ll c)

{

	if(a<=l&&r<=b)

	{

		ll ret=s[x]-(r-l+1)*c;

		ts[x]=0,sm[x]=tag[x]=c,s[x]=(r-l+1)*c;

		return ret;

	}

	pushdown(l,r,x);

	int mid=l+r>>1;

	ll ret=0;

	if(a<=mid)	ret+=updata(l,mid,lson,a,b,c);

	if(b>mid)	ret+=updata(mid+1,r,rson,a,b,c);

	pushup(x);

	return ret;

}

int getpre(int l,int r,int x,ll a)

{

	if(sm[x]>=a)	return l-1;

	if(l==r)	return l;

	pushdown(l,r,x);

	int mid=l+r>>1;

	if(sm[rson]<a)	return getpre(mid+1,r,rson,a);

	return getpre(l,mid,lson,a);

}

ll rd()

{

	ll ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd();

	int i;

	for(i=1;i<=n;i++)	A[i]=rd();

	sort(A+1,A+n+1);

	build(1,n,1);

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

	{

		D[i]=rd(),B=rd();

		ts[1]+=D[i]-D[i-1],s[1]+=siz[1]*(D[i]-D[i-1]),sm[1]+=A[1]*(D[i]-D[i-1]);

		int a=getpre(1,n,1,B);

		if(a<n)	printf("%lld\n",updata(1,n,1,a+1,n,B));

		else	printf("0\n");

	}

	return 0;

}//4 4 1 2 4 3 1 1 2 2 3 0 4 4

Byteasar