M_sea

洛谷4064 [JXOI2017]加法
LuoguBZOJ分析第一眼想到二分答案。 然后我就不会了首先以 $l$ 为第一关键字、$r$ 为第二关键字将所有...
扫描右侧二维码阅读全文
15
2019/03

洛谷4064 [JXOI2017]加法

Luogu

BZOJ

分析

第一眼想到二分答案。 然后我就不会了

首先以 $l$ 为第一关键字、$r$ 为第二关键字将所有区间排序。

假设现在二分出了一个答案 $mid$ 。

贪心地想,我们只会在不得不给一个区间加上 $a$ 时给它加上 $a$ 。

于是从左到右扫,如果一个点没有达到 $mid$ 的话,那么从之前的区间中选一个加上 $a$ 。

再贪心地想,选出的区间一定是 $r$ 最大的,这样子才能覆盖更多的点。

于是可以用一个堆来维护 $r$ 最大的区间,每次取出即可。

然后还要维护一个树状数组来支持区间加、单点查询。

考虑不可行的情况:

  • 没有线段能够覆盖到当前这个没有达到 $mid$ 的点。
  • 用的次数超过了 $k$ 。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m,v,k;
int a[N];

struct seg { int l,r; } s[N];
bool operator <(seg a,seg b) { return a.l==b.l?a.r<b.r:a.l<b.l; }
struct heapnode { int l,r; };
bool operator <(heapnode a,heapnode b) { return a.r==b.r?a.l<b.l:a.r<b.r; }

int c[N];
inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    for (;x<=n;x+=lowbit(x)) c[x]+=y;
}
inline int get(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

inline int check(int mid) {
    priority_queue<heapnode> heap;
    memset(c,0,sizeof(c));
    for (re int i=1;i<=n;++i) add(i,a[i]),add(i+1,-a[i]);
    int now=0;
    for (re int i=1,j=1;i<=n;++i) {
        while (j<=m&&s[j].l<=i) heap.push((heapnode){s[j].l,s[j].r}),++j;
        while (get(i)<mid) {
            if (heap.empty()) return 0;
            heapnode t=heap.top(); heap.pop();
            if (t.r<i) return 0;
            add(t.l,v),add(t.r+1,-v),++now;
            if (now>k) return 0;
        }
    }
    return 1;
}

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),k=read(),v=read();
        for (re int i=1;i<=n;++i) a[i]=read();
        for (re int i=1;i<=m;++i) s[i].l=read(),s[i].r=read();
        sort(s+1,s+m+1);
        int L=1e9,R;
        for (re int i=1;i<=n;++i) L=min(L,a[i]);
        R=L+v*k;
        while (L<R) {
            int mid=(L+R+1)>>1;
            if (check(mid)) L=mid;
            else R=mid-1;
        }
        printf("%d\n",L);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 13 PM

3 条评论

  1. 冒泡ioa

    为什么45行i只用枚举到m呢(ó﹏ò。)

    1. M_sea
      @冒泡ioa

      写错了...应该是n的...(这也能过?)

      1. 冒泡ioa
        @M_sea

        是啊 写成m还更快XD

发表评论