初级守护
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
bool check(ll target, const vector<int>& arr, const vector<pair<int, int>>& intervals, int k, int a) {
int n = arr.size();
vector<ll> need(n + 1, 0);
vector<ll> diff(n + 2, 0);
// 计算每个位置需要的操作次数
for (int i = 1; i <= n; i++) {
if (arr[i - 1] >= target) {
need[i] = 0;
} else {
ll gap = target - arr[i - 1];
need[i] = (gap + a - 1) / a; // 向上取整
}
}
// 构建区间索引
vector<vector<int>> end_at(n + 2);
for (int i = 0; i < intervals.size(); i++) {
end_at[intervals[i].second].push_back(i);
}
int used = 0;
ll current_add = 0;
priority_queue<int> pq; // 存储区间的结束位置
for (int i = 1; i <= n; i++) {
current_add += diff[i];
// 将当前点结束的区间加入优先队列
for (int idx : end_at[i]) {
pq.push(intervals[idx].second);
}
// 当前点还需要增加的操作次数
ll remaining = need[i] - current_add;
// 如果还需要更多操作
while (remaining > 0 && !pq.empty()) {
int r = pq.top();
pq.pop();
used++;
if (used > k) return false;
// 应用区间操作
current_add++;
if (r + 1 <= n) diff[r + 1]--;
remaining--;
}
if (current_add < need[i]) {
return false;
}
}
return used <= k;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, k, a;
cin >> n >> m >> k >> a;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<pair<int, int>> intervals(m);
for (int i = 0; i < m; i++) {
cin >> intervals[i].first >> intervals[i].second;
}
// 确定二分范围
ll left = *min_element(arr.begin(), arr.end());
ll right = left + (ll)k * a + 1;
ll ans = left;
while (left <= right) {
ll mid = left + (right - left) / 2;
if (check(mid, arr, intervals, k, a)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << ans << "\n";
}
return 0;
}
