[JXOI2017] 加法 题解

[JXOI2017] 加法

最小值最大，一眼二分。贪心地，每次尽量对包含当前序列最小值的区间做加法操作，也就是说，对于当前二分的答案 \(x\)，任何的 \(A_i<x\) 都需要被操作。

从左到右地考虑答案。我们认为当前点之前的所有值都已经满足条件，于是我们只需考虑每次区间对当前点之后答案造成的贡献。于是我们将所有区间按左端点为第一关键字排序，而在左端点相同的所有区间当中，我们选择右端点最靠右的区间，以覆盖更多的元素。

每一次从 \(i-1\) 到 \(i\) 的过程中，加入左端点在 \(i\) 的区间并删除右端点在 \(i-1\) 的区间，就可以动态维护覆盖当前点的区间。用一个以右端点为第一关键字排序的优先队列维护右端点最靠右的区间，每次对于这个区间加 \(a\)，直到当前点的值 \(\ge x\)。任何时候若没有能覆盖 “需要被操作” 的点的区间，或所有区间加完了之后这个点仍 \(<x\)，则不可行；反之当前答案可行。

需要一个支持区间修改、单点查询的数据结构，线段树和树状数组皆可。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=2e5+5;
int T,n,m,k,A;
ll a[MAXN];
struct{
	ll st[MAXN<<2],lazy[MAXN<<2];
	#define lp p<<1
	#define rp p<<1|1
	#define mid ((s+t)>>1)
	void build(int s,int t,int p){
		st[p]=lazy[p]=0;
		if(s==t)return st[p]=a[s],void();
		build(s,mid,lp),build(mid+1,t,rp);
		st[p]=st[lp]+st[rp];
	}
	void pushdown(int s,int t,int p){
		if(!lazy[p]) return;
		st[lp]+=(mid-s+1)*lazy[p],st[rp]+=(t-mid)*lazy[p];
		lazy[lp]+=lazy[p],lazy[rp]+=lazy[p];
		lazy[p]=0;
	}
	void mdf(int l,int r,ll k,int s=1,int t=n,int p=1){
		if(l<=s&&t<=r) return st[p]+=(t-s+1)*k,lazy[p]+=k,void();
		pushdown(s,t,p);
		if(l<=mid) mdf(l,r,k,s,mid,lp);
		if(mid<r) mdf(l,r,k,mid+1,t,rp);
		st[p]=st[lp]+st[rp];
	}
	ll sum(int x,int s=1,int t=n,int p=1){
		if(s==t) return st[p];
		pushdown(s,t,p);
		if(x<=mid) return sum(x,s,mid,lp);
		return sum(x,mid+1,t,rp);
	}
	#undef mid
}ST;
struct SH{
	int l,r;
	bool operator<(const SH&x)const{
		return r<x.r;
	}
}p[MAXN],t;

bool check(ll x){
	priority_queue<SH>q;
	ST.build(1,n,1);
	int lst=1,cnt=0;
	for(int i=1;i<=n;++i){
		while(lst<=m&&p[lst].l<=i) q.emplace(p[lst++]);
		while(!q.empty()&&ST.sum(i)<x){
			do t=q.top(),q.pop();
			while(!q.empty()&&t.r<i);
			if(t.r<i||++cnt>k) return 0;
			ST.mdf(t.l,t.r,A);
		}
		if(ST.sum(i)<x) return 0;
	}
	return 1;
}

int main(){
	T=read();
	while(T--){
		n=read(),m=read(),k=read(),A=read();
		ll l=2e18,r=0;
		for(int i=1;i<=n;++i) a[i]=read(),l=min(l,a[i]),r=max(r,a[i]);
		r+=k*A;
		for(int i=1;i<=m;++i) p[i]={read(),read()};
		sort(p+1,p+m+1,[&](const SH&x,const SH&y){
			return x.l<y.l;
		});
		ll mid,ans=l;
		while(l<=r){
			mid=(l+r)>>1;
			if(check(mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		write(ans);
	}
	return fw,0;
}