求调

AC #1 #2 #5

#include<bits/stdc++.h>
using namespace std;
#define pl (p<<1)
#define pr (p<<1|1)
const int N=2e5+10;
struct node{int l,r;}b[N];bool operator<(node a,node b){return a.r<b.r;}
int T,n,m,k,a,A[N];priority_queue<node>q;
struct seg{
    struct Tree{int add,sum;}tr[N<<2];
    void pushup(int p){tr[p].sum=tr[pl].sum+tr[pr].sum;}
    void add(int p,int v,int len){tr[p].sum+=v*len,tr[p].add+=v;}
    void pushdown(int p,int len1,int len2){if(tr[p].add)add(pl,tr[p].add,len1),add(pr,tr[p].add,len2),tr[p].add=0;}
    void build(int l,int r,int p){
        if(l==r)return tr[p]={0,A[l]},void();
        int mid=l+r>>1;build(l,mid,pl),build(mid+1,r,pr),pushup(p);
    }void update(int l,int r,int le,int ri,int v,int p){
        if(l>=le&&r<=ri)return add(p,v,r-l+1);
        int mid=l+r>>1;pushdown(p,mid-l+1,r-mid);
        if(le<=mid)update(l,mid,le,ri,v,pl);
        if(ri>mid)update(mid+1,r,le,ri,v,pr);
        pushup(p);
    }int query(int l,int r,int le,int ri,int p){
        if(l>=le&&r<=ri)return tr[p].sum;
        int mid=l+r>>1,ret=0;pushdown(p,mid-l+1,r-mid);
        if(le<=mid)ret+=query(l,mid,le,ri,pl);
        if(ri>mid)ret+=query(mid+1,r,le,ri,pr);
        return ret;
    }
}t;
bool check(int mid){
    t.build(1,n,1);int cnt=0;
    while(!q.empty())q.pop();
    for(int i=1,j=1;i<=n;i++){
        while(b[j].l<=i&&j<=m)q.push(b[j++]);
        while(t.query(1,n,i,i,1)<mid){
            if(q.empty())return 0;
            if(q.top().r<i)return q.pop(),0;
            t.update(1,n,q.top().l,q.top().r,a,1),q.pop();
            if(++cnt>k)return 0;
        }
    }return 1;
}int main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>k>>a;int l=2e9,r=-2e9;
        for(int i=1;i<=n;i++)cin>>A[i],l=min(l,A[i]);
        for(int i=1;i<=m;i++)cin>>b[i].l>>b[i].r;
        sort(b+1,b+m+1,[](node x,node y){return x.l<y.l;});
        r=l+k*a;
        for(int mid;l<r;check(mid=l+r+1>>1)?l=mid:r=mid-1);
        cout<<l<<'\n';
    }return 0;
}