「bzoj4293」「PA2015」Siano - 线段树+二分

题目大意

给你一些草，每一个草每天会增加$a[i]$的长度，再给出一些操作，表示在第$d[j]$天将$\,\ge b[j]$的草全部收割使其长度变为$b[j]$，输出收割得到的草的总长度。

---

初步想法

嗯？这不是我们刚刚研究过的Segment Tree Beats？
区间增加，区间取min？

然而可以发现并没有这么麻烦，为什么呢？因为这道题不是对区间操作，而是直接对全局操作。
那么我们可以用一种比较简单的方法处理它：
既然是全局操作，那么草与草之间是无序的，我们可以直接对草按照生长速度进行排序。可以发现，排完序后无论如何操作，草的长度总是单调不降的。
既然如此，我们就可以在每一次操作前对全局做一次区间增加操作，再在线段树中二分找到临界点，将临界点后面的长度全部置为$b[j]$即可。

---

具体实现

线段树维护以下信息：

• 区间总高度
• 区间最大/最小高度
• 区间总生长速度
• 区间最大/最小生长速度
• 增加的lazy标记，修改的lazy标记。

---

接着只需要维护一下修改和增加操作就可以了，注意双标记间的兼容。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=500005;
struct Tree {
	int left,right;
	LL sum,min,max; //高度
	LL asum,amin,amax; //生长能力 
	LL lazy1,lazy2; //lazy1增加 lazy2修改 
	Tree(int l=0,int r=0,LL _asum=0,LL _amin=0,LL _amax=0):left(l),right(r),asum(_asum),amin(_amin),amax(_amax) {
		sum=max=min=lazy1=0;
		lazy2=-1;
	}
};
struct Segment_Tree {
	Tree tree[maxn*4];
	#define ls index<<1
	#define rs index<<1|1
	void build(int index,int Left,int Right,LL* a) {
		tree[index]=Tree(Left,Right);
		if(Left==Right) {
			tree[index]=Tree(Left,Right,a[Left],a[Left],a[Left]);
			return;
		}
		int mid=(Left+Right)>>1;
		build(ls,Left,mid,a);
		build(rs,mid+1,Right,a);
		//维护生长能力 
		tree[index].asum=tree[ls].asum+tree[rs].asum;
		tree[index].amin=a[Left];
		tree[index].amax=a[Right];
	}
	void push_up(int index) { //维护值 
		tree[index].sum=tree[ls].sum+tree[rs].sum;
		tree[index].max=max(tree[ls].max,tree[rs].max);
		tree[index].min=min(tree[ls].min,tree[rs].min);
	}
	void modify(int index,LL val) {
		tree[index].sum=val*(tree[index].right-tree[index].left+1);
		tree[index].min=tree[index].max=tree[index].lazy2=val;
		tree[index].lazy1=0; //修改后原来的添加无效 
	}
	void add(int index,LL t) {
		tree[index].lazy1+=t;
		tree[index].sum+=tree[index].asum*t;
		tree[index].min+=tree[index].amin*t;
		tree[index].max+=tree[index].amax*t;
	}
	void push_down(int index) {
		if(tree[index].lazy2!=-1) {
			modify(ls,tree[index].lazy2);
			modify(rs,tree[index].lazy2);
			tree[index].lazy2=-1;
		}
		if(tree[index].lazy1) {
			add(ls,tree[index].lazy1);
			add(rs,tree[index].lazy1);
			tree[index].lazy1=0;
		}
	}
	LL solve(int index,LL limit) {
		if(tree[index].max<limit)return 0;
		if(tree[index].min>=limit) {
			LL tmp=tree[index].sum;
			modify(index,limit);
			return tmp-tree[index].sum;
		}
		push_down(index);
		LL sum=solve(ls,limit)+solve(rs,limit);
		push_up(index);
		return sum;
	}
} st;
int n,m;
LL a[maxn];
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	sort(a+1,a+n+1);
	st.build(1,1,n,a);
	LL last=0;
	for(int i=1; i<=m; i++) {
		LL t=Get_Int(),b=Get_Int();
		st.add(1,t-last);
		last=t;
		printf("%lld\n",st.solve(1,b));
	}
	return 0;
}