题解 传送门

按照套路

先把区间按左端点排序
然后再来思考怎么使最小值最大???
.
.
.
想到了啥???

二分答案!!!

所以思路就很清晰了
先二分答案
对于每个二分出来的值去check:
1.扫一遍点
2.对于达不到这个值的每个点,把区间按右端点从大到小依次加上,知道该点的值满足条件
3.同时记录所花费的区间个数
4.如果2和3有任意一个不满足,即是不符合的

对于覆盖了当前点的区间的右端点的大小,可以用堆维护一下 (倒是跟 这题 蛮像的)
加区间的操作直接用树状数组就好了

小细节: 由于我码风丑陋,数组开到4e5就TLE飞了

代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
#define in inline
#define get getchar()
#define db double
in int read()
{
    int t=0,x=1; char ch=get;
    while ((ch<'0' || ch>'9') && ch!='-') ch=get;
    if (ch=='-') ch=get, x=-1;
    while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;
    return t*x;
}
const int _=4e5+5;
struct region{
    int x,y;
}r[_];
int n,m,k,add,a[_],sum[_];
in int cmp(region a,region b)
{
    return a.x<b.x;
}

in int lowbit(int x){
    return x&-x;
}
in void insert(int x,int y)
{
    for(re int i=x;i<=n;i+=lowbit(i)) sum[i]+=y;
}
in int query(int x)
{
    int ans=0;
    for(re int i=x;i>=1;i-=lowbit(i)) ans+=sum[i];
    return ans;
} //树状数组基本操作

in int check(int x)
{
    priority_queue<int>q; //存满足条件的区间的右端点
    int j=1,tot=0;
    memset(sum,0,sizeof(sum));
    for (re int i=1;i<=n;i++)
    {
        int kkk=query(i);//当前点已经加上了的区间的值
        while(r[j].x<=i&&j<=m)
        {
            q.push(r[j].y);
            j++;
        } //当前区间满足条件,将其右端点压入堆
        while(!q.empty() && kkk+a[i]<x&&q.top()>=i&&tot<=k) //当前点的值太小,需要加上一些区间
        {
            insert(i,add);
            insert(q.top()+1,-add); 
            kkk=query(i); //树状数组基于差分实现的区间修改,单点查询 
            q.pop(); //记得把此区间弹掉
            tot++; //记录使用的区间个数
        }
        if(kkk+a[i]<x||tot>k)return 0;
    }
    return 1;
}
int main()
{
    int t=read();
    while(t--)
    {
        n=read(),m=read(),k=read(),add=read();
        for (re int i=1;i<=n;i++) a[i]=read();
        for (re int i=1;i<=m;i++)
            r[i].x=read(),r[i].y=read();
        sort (r+1,r+1+m,cmp);
        int L=add,R=2e9,res,mid;
        while (L<=R)
        {
            mid=(L+R)>>1;
            if (check(mid)) res=mid,L=mid+1;
            else R=mid-1;
        } //二分答案
        cout<<res<<endl;
    }
}

有史以来,yzhx第一次写这么多注释

Luogu P4064 [JXOI2017]加法

原文：https://www.cnblogs.com/yzhx/p/10656039.html