最小值最大,考虑二分答案,问题转为判断最小值是否能 \(\ge x\)。
假如 \(a_i\ge x\),那我们肯定不管;假如 \(a_i<x\),那最好能让选择的区间 \(r\) 值更大,用优先队列维护即可。区间增幅可以用树状数组维护。
时间复杂度 \(O(n\log^2n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int t,n,m,k,ad,a[N],c[N];
priority_queue<int>q;
vector<int>g[N];
void add(int x){
for(;x<=n;x+=x&-x)
c[x]+=ad;
}int sum(int x){
int re=0;
for(;x;x-=x&-x)
re+=c[x];
return re;
}int check(int x){
for(int i=1;i<=n;i++) c[i]=0;
while(q.size()) q.pop();
for(int i=1,l=k;i<=n;i++){
for(auto j:g[i]) q.push(j);
int nw=a[i]+sum(n)-sum(i-1);
while(nw<x&&q.size()&&l&&q.top()>=i)
nw+=ad,add(q.top()),q.pop(),l--;
if(nw<x) return 0;
}return 1;
}void solve(){
for(int i=1;i<=n;i++) g[i].clear();
cin>>n>>m>>k>>ad;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1,l,r;i<=m;i++)
cin>>l>>r,g[l].push_back(r);
int l=0,r=2e8,ans;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))
ans=mid,l=mid+1;
else r=mid-1;
}cout<<ans<<"\n";
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--) solve();
return 0;
}
标签:JXOI2017,ad,int,题解,long,ge,加法
From: https://www.cnblogs.com/chang-an-22-lyh/p/18538185/jxoi2017-jia_fa-tj