自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:56:06，当前版本为作者最后更新于2018-03-28 08:01:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实不需要树状数组的……

很有意思的一道二分题

熟练的诸位想必马上反应出二分答案了吧……

因为题目中是要求最大化整个序列的最小值，那么我们可以二分这个最小值

显然这个最小值的取值范围是在$[min(A_{i}),min(A_{i})+ma]$之间，然后就可以二分了~

现在我们二分了一个答案mid出来，我们呢要判断这个mid合不合法

我们发现每个点需要被覆盖的次数不一样，有些点甚至完全不需要被覆盖，我们需要决策出一个最小的方案

那么我们怎么决策呢？当然是贪心了

大概的思路是，我们只有在不得不使用一次加法的时候才去使用加法，否则不使用

另外，我们希望后边的决策不会影响前边的决策

这样的话我们才可以放心的使用贪心

那么我们可以这样做，把一个线段拆成一个左端点和一个右端点，和我们的序列点一起排序，最后形成一个长度为$n+2m$的决策序列

现在我们从左到右的扫这个决策序列，保证同一位置的左端点在序列点前，右端点在序列点后

如果这个点是一个左端点，我们插入一个线段到某个数据结构中存储

如果这个点是一个决策点，我们计算它的值还需要加几次到达mid，然后查找我们的数据结构里有多少合法的线段

显然有一个贪心策略是，因为现在排好序了，所以扫到这个序列点时，前边的序列已经全部合法，因此数据结构中现存线段的左端点在哪里变得毫无意义，我们只需要优先选择右端点最远的点进行加法就可以了

所以我们优先选择数据结构中最远的右端点，进行若干次区间加操作即可

现在让我们来看右端点，如果直白的想一下的话，我们会觉得这个点的作用是删除一个线段，但是我们发现前面指的某种数据结构明显是一个堆，而且我们呢也不需要真的插入一个线段，插入一个右端点足矣。

那么我们会发现我们完全可以使用惰性删除法，就是说在检查这个堆的时候，我们呢可以检测这个右端点是否在这个决策点的左边，如果在左边我们认为堆为空，可以return false了

发现好像没有右端点什么事？

但是右端点本来就不是用来删除的啊……，还记得我们需要进行区间加操作吗？

好像需要维护一个线段树/树状数组，真是麻烦

我们都知道二维扫描线可以将二维问题变成一个一维问题，用一维数据结构来维护，那么我们现在要解决的问题是一个一维区间加问题，我们当然可以用一个一维扫描线，把这个一维问题变成一个零维问题，用零维数据结构——一个变量来维护

具体来讲，当你需要进行一次区间加操作的时候，并不进行区间加，而是仅仅在一个临时变量flow上+a，同时标记上这个区间已选，我们每次扫到一个决策点的时候先把它的值+flow，对应着这个点承受的区间加操作

之后当我扫到一个右端点时，我们要"删除"这个区间，我们检查一下这个区间有没有被选中，如果被选了，我们就把flow-a，代表这个区间加已经结束，如果没被选就什么也不做

所以我们就这样愉快的消掉了一个数据结构，全程只需要一个priority_queue就行了

算法复杂度$O((n+m)log(n+m)log(ma))$，大致是$O(nlog^{2}n)$的(实际上跑的飞起)

上代码~

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=2*1e5+10;typedef long long ll;
int n;int m;ll a;int k;int T;
struct opt//操作结构体 
{
    ll val;int tp;int pos;//val对于序列点是点值，对于线段点是编号 
    friend bool operator <(opt a,opt b){return a.pos+a.tp/3.0<b.pos+b.tp/3.0;}
}op[3*N];int cnt;int book[N];int r[N];ll lf=0x7f7f7f7f;ll ri;
struct data{int v;friend bool operator <(data a,data b){return r[a.v]<r[b.v];}};
priority_queue <data> pq;//这里写了一个O(1)的清空函数 
inline void clear(priority_queue <data>& pq){priority_queue <data> emp;swap(emp,pq);}
inline bool jud(ll mid)
{
    ll flow=0;int tot=0;
    for(int i=1;i<=cnt;i++)
    {
        if(op[i].tp==0){pq.push((data){op[i].val});}//插入左端点 
        else if(op[i].tp==1)
        {
            ll ned=mid-op[i].val-flow;if(ned<0)continue;//如果比mid大可以continue了 
            ll ch=(ned+a-1)/a;if(tot+ch>k){return false;}//如果超了限制的话可以拍false了 
            for(;!pq.empty()&&ch;pq.pop())
            {
                int v=(pq.top()).v;
                if(r[v]<op[i].pos){return false;}//如果此时堆为空也可以拍false了 
                else {book[v]=1;flow+=a;ch--;tot++;}//区间+a 
            }if(ch>0){return false;}//如果没加完也可以拍false了 
        }else{flow-=book[op[i].val]*a;}//检查下这个区间有没有被选中 
    }return true;//如果全部通过就return true 
} 
inline void solve()
{
    scanf("%d%d%d%d",&n,&m,&k,&a);
    for(int i=1;i<=n;i++)//插入序列点 
    {int t;scanf("%lld",&t);op[++cnt]=(opt){t,1,i};lf=min(lf,(ll)t);}
    for(int i=1;i<=m;i++)//插入线段点 
    {
        scanf("%d",&r[i]);op[++cnt]=(opt){i,0,r[i]};
        scanf("%d",&r[i]);op[++cnt]=(opt){i,2,r[i]};
    }sort(op+1,op+cnt+1);ri=lf+m*a;//计算左右区间 
    while(lf!=ri)//二分答案，记得清空 
    {
        ll mid=(lf+ri+1)/2;if(jud(mid)){lf=mid;}else {ri=mid-1;}
        clear(pq);for(int i=1;i<=m;i++){book[i]=0;}
    }printf("%lld\n",lf);cnt=0;lf=0x7f7f7f7f;//清空一些东西 
}
int main(){scanf("%d",&T);for(int z=1;z<=T;z++){solve();}return 0;}//拜拜程序~