Codeforces 460C 二分结果+线段树维护

发现最近碰到好多次二分结果的题目，上次多校也是，被我很机智的快速过了，这个思想确实非常不错。在正面求比较难处理的时候，二分结果再判断是否有效往往柳暗花明。

这个题目给定n个数字的序列，可以操作m次，每次要操作w个连续的数字，每次的操作将使得该段连续数字的数都+1，最后求整个序列最小值的最大值

求最小值最大，明显的二分结果的题目，我一开始还是在ACdream那个群里看到这个题，说是二分+线段树的题目，我就来做了一下。。首先二分部分很容易，下界就是初始序列的最小值，上界就是下界+m，至于怎么判断这个就要想一下，我一开始还觉得不用线段树，因为我每次枚举完结果，对整个序列扫一遍，对不符合要求的数+到正好符号要求不就行了。

不过这个里面因为是要+连续一段，你普通的找到一个不符合条件的数，然后对他以及他之后的w-1个数都进行一次加法，很耗时啊，所以这个就是为什么要用线段树，其实我觉得用扫描线估计也可以，对某个起始点设置+1，起始点+w-1设置为-1，然后用个东西维护，++--的，估计也可以。反正最后用的线段树，普通的区间增，单点查询。

一开始还担心复杂度，不过还行的感觉，每次二分都要重新建树，这里就是 logN*N*logN,对二分结果进行判断，需要单点查询以及区间更新，这里是2*logN*logN，所以总的就是

logN*logN*（N+2)的复杂度，N最大为10的五次方，logN不超过20

#include <iostream>

#include <cstdio>

#include <cstring>

#define lson rt<<1,l,mid

#define rson rt<<1|1,mid+1,r

#define LL __int64

using namespace std;

const int  N = 100000+10;

int n,m,w;

LL d[N<<2],flag[N<<2],A[N];

LL mini;

void up(int rt)

{

    d[rt]=min(d[rt<<1],d[rt<<1|1]);

}

void build(int rt,int l,int r)

{

    flag[rt]=0;

    if (l>=r){

        d[rt]=A[l];

        //cout<<l<<" "<<A[l]<<endl;

        return;

    }

    int mid=(l+r)>>1;

    build(lson);

    build(rson);

    up(rt);

}

void pushdown(int rt,int l,int r)

{

    if (flag[rt]==0) return;

    d[rt<<1]+=flag[rt];

    d[rt<<1|1]+=flag[rt];

    flag[rt<<1]+=flag[rt];

    flag[rt<<1|1]+=flag[rt];

    flag[rt]=0;

}

LL query(int loc,int rt,int l,int r)

{

    if (l==r) return d[rt];

    int mid=(l+r)>>1;

    pushdown(rt,l,r);

    if (loc<=mid) return query(loc,lson);

    else return query(loc,rson);

}

void update(LL val,int L,int R,int rt,int l,int r)

{

    if (L<=l && r<=R){

        d[rt]+=val;

        flag[rt]+=val;

        return;

    }

    pushdown(rt,l,r);

    int mid=(l+r)>>1;

    if (L<=mid) update(val,L,R,lson);

    if (R>mid) update(val,L,R,rson);

    up(rt);

}

bool judge(LL x)

{

    LL tmp=m;

    for (int i=1;i<=n;i++){

        LL now=query(i,1,1,n);

       // cout<<"Test "<<i<<endl;

       // cout<<now<<endl;

        if (now<x){

           if (x-now>tmp) return 0;

           else {

             update(x-now,i,min(i+w-1,n),1,1,n);

             tmp-=x-now;

           }

        }

    }

    return 1;

}

int main()

{

    while (scanf("%d%d%d",&n,&m,&w)!=EOF)

    {

        mini=-1;

        for (int i=1;i<=n;i++){

            scanf("%I64d",&A[i]);

            //cout<<i<<" "<<A[i]<<endl;

            if (mini==-1) mini=A[i];

            else mini=min(A[i],mini);

        }

        LL L=mini,R=mini+(LL)m,mid;

        while (L<R){

            build(1,1,n);

            mid=R-(R-L)/2;

           // cout<<L<<" "<<mid<<" "<<R<<endl;

            if (judge(mid)) {L=mid;}

            else {R=mid-1;}

        }

        printf("%I64d\n",L);

    }

    return 0;

}

巴特西

Codeforces 460C 二分结果+线段树维护

最新文章

热门文章