题目传送门
题意分析
注意到「最小值尽可能的大」。
一般对于这种最值的最值的问题，都可以套一层二分答案。——xxy
考虑二分答案。
二分答案的原因
一直没想明白，直到我在模拟赛上打了 $\text{1.5h}$ 建了 $3$ 棵线段树维护的贪心假了后，终于想起来二分答案。
最值具有单调性，最值的最值同样有。
例如最大值 $x$ 的最小值 $y$，我们二分最大值 $x$，则当 $x\geq y$ 的时候，其性质不变。
那么我们本质上就是将最优性问题转化为了判定性问题——而这往往更为容易。
二分序列最小值 \(\textit{mid}\)。考虑如何高效判断 \(\textit{mid}\) 是否可行。容易得到 \(A_i\) 需要加上多少个 \(a\)，即：
\[\textit{cnt}_i=\left\lceil\dfrac{\textit{mid}-A_i}{a}\right\rceil=\left\lfloor\dfrac{\textit{mid}-A_i+a-1}{a}\right\rfloor
\]
之后就是判断能否选择至多 \(k\) 条线段，每条线段 \([l,r]\) 都使 \(\forall i\in[l,r],\textit{cnt}_i\leftarrow \textit{cnt}_i-1\)，最终能否使得所有 \(\textit{cnt}_i\) 都小于等于 \(0\)。
因为这是判定性问题，所有点都要被满足，因此直接扫一遍。
考虑覆盖了 \(i\) 的线段，我们期望优先选择一条尽可能往右覆盖的线段，这样更优（左边已经覆盖完了）。因此用堆维护右端点，扫到一个左端点就将其加入堆。
时间复杂度 \(\mathcal O(n\log n\log V)\)，其中 \(V\) 为值域。
AC 代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
constexpr const int N=2e5,M=2e5;
vector<int>R[N+1];
int n,m,k,add,a[N+1];
struct segTree{struct node{int l,r;int max,tag;}t[N<<2|1];void up(int p){t[p].max=t[p<<1].max+t[p<<1|1].max;}void build(int p,int l,int r,int a[]){t[p]={l,r};if(l==r){t[p].max=a[l];return;}int mid=l+r>>1;build(p<<1,l,mid,a);build(p<<1|1,mid+1,r,a);up(p);}void down(int p){if(t[p].tag){t[p<<1].max+=t[p].tag;t[p<<1].tag+=t[p].tag;t[p<<1|1].max+=t[p].tag;t[p<<1|1].tag+=t[p].tag;t[p].tag=0;}}void add(int p,int l,int r,int x){if(l<=t[p].l&&t[p].r<=r){t[p].max+=x;t[p].tag+=x;return;}down(p);if(l<=t[p<<1].r){add(p<<1,l,r,x);}if(t[p<<1|1].l<=r){add(p<<1|1,l,r,x);}up(p);}int query(int p,int x){if(t[p].l==t[p].r){return t[p].max;}down(p);if(x<=t[p<<1].r){return query(p<<1,x);}else{return query(p<<1|1,x);}}
}t;
bool check(int mid){static int cnt[N+1];for(int i=1;i<=n;i++){cnt[i]=(mid-a[i]+add-1)/add;}t.build(1,1,n,cnt);priority_queue<int>q;int pl=0;for(int i=1;i<=n;i++){for(int r:R[i]){q.push(r);}while(t.query(1,i)>0){if(!q.size()){return false;}int r=q.top();if(r<i||pl>=k){return false;}q.pop();pl++;t.add(1,1,r,-1);}}return true;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m>>k>>add;for(int i=1;i<=n;i++){cin>>a[i];R[i].resize(0);}for(int i=1;i<=m;i++){int l,r;cin>>l>>r;R[l].push_back(r);}int l=a[1],ans=-1;for(int i=2;i<=n;i++){l=min(l,a[i]);}int r=l+k*add;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<ans<<'\n';}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}