题意分析
注意到「最小值尽可能的大」。
一般对于这种最值的最值的问题，都可以套一层二分答案。——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 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//#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;
}
