牛客网中南林业科技大学第十一届程序设计大赛J题二分+线段树

https://www.nowcoder.com/acm/contest/124#question

题意找第一个不小于K的数的下标，然后对它前一个数加一

解析我们可以维护一个最大值数组 1到 i的最大值就是max[ i ] 二分找到最左边的值但是找到的前一个加1 要用线段树来维护最大值

但是这么写会超时。。。

超时代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=,maxn=1e6+;

int sum[maxn<<];

int a[maxn],n,m;

void PushUP(int rt)

{

    sum[rt]=max(sum[rt<<],sum[rt<<|]);

}

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

{

    if(l==r)

    {

        sum[rt]=a[l];

        return;

    }

    int m=(l+r)>>;

    Build(l,m,rt<<);

    Build(m+,r,rt<<|);

    PushUP(rt);

}

void Update(int L,int C,int l,int r,int rt)

{

    if(l==r)

    {

        sum[rt]+=C;

        return;

    }

    int m=(l+r)>>;

    if(L<=m)

        Update(L,C,l,m,rt<<);

    else

        Update(L,C,m+,r,rt<<|);

    PushUP(rt);

}

int Query(int L,int R,int l,int r,int rt)

{

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

    {

        return sum[rt];

    }

    int m=(l+r)>>;

    int ans=-;

    if(L<=m)

        ans=max(ans,Query(L,R,l,m,rt<<));

    if(R>m)

        ans=max(ans,Query(L,R,m+,r,rt<<|));

    return ans;

}

int main()

{

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

    {

        memset(sum,,sizeof(sum));

        memset(a,,sizeof(a));

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

        {

            scanf("%d",&a[i]);

        }

        Build(,n,);

        int l,r,k;

        while(m--)

        {

            l=,r=n;

            scanf("%d",&k);

            //cout<<Query(1,n,1,n,1)<<endl;

            if(Query(,n,,n,)<k)

            {

                printf("are you ok\n");

                continue;

            }

            while(l<=r)

            {

                int mid=(l+r)>>;

               // cout<<mid<<" "<<Query(1,mid,1,n,1)<<endl;

                if(Query(,mid,,n,)>=k)

                    r=mid-;

                else

                    l=mid+;

            }

            printf("%d\n",l-);

            if(l-)

                Update(l-,,,n,);

        }

    }

}

q的询问比较多应该是卡了常数我们要优化一下因为线段树查询的时候就是二分区间最大值是递增的我们直接利用这个特点来操作

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=,maxn=1e6+;

int sum[maxn<<];

int a[maxn],n,m;

void PushUP(int rt)

{

    sum[rt]=max(sum[rt<<],sum[rt<<|]);

}

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

{

    if(l==r)

    {

        sum[rt]=a[l];

        return;

    }

    int m=(l+r)>>;

    Build(l,m,rt<<);

    Build(m+,r,rt<<|);

    PushUP(rt);

}

void Update(int L,int C,int l,int r,int rt)

{

    if(l==r)

    {

        sum[rt]+=C;

        return;

    }

    int m=(l+r)>>;

    if(L<=m)

        Update(L,C,l,m,rt<<);

    else

        Update(L,C,m+,r,rt<<|);

    PushUP(rt);

}

int query(int L,int R,int l,int r,int rt,int p)

{

    if(l==r)

    {

        return l;

    }

    int m=(l+r)>>;

    if(sum[rt<<]>=p)                    //二分查询

        return query(L,R,l,m,rt<<,p);

    return query(L,R,m+,r,rt<<|,p);

}

int main()

{

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

    {

        memset(sum,,sizeof(sum));

        memset(a,,sizeof(a));

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

        {

            scanf("%d",&a[i]);

        }

        Build(,n,);

        int l,r,k;

        while(m--)

        {

            l=,r=n;

            scanf("%d",&k);

            if(sum[]<k)

            {

                printf("are you ok\n");

                continue;

            }

            int ans=query(,n,,n,,k);

            printf("%d\n",ans-);

            if(ans-)

                Update(ans-,,,n,);

        }

    }

}

其实还有更简单的做法因为修改的是前一个值而且找的是满足条件中最左边的所以前一个+1 并不会影响数组的单调性变得只有前面一个的最大值更新一下就好了

#include<bits/stdc++.h>

using namespace std;

int a[],b[];

int n,q,k;

int main()

{

    while(~scanf("%d%d",&n,&q))

    {

        int mx=;

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

        {

            scanf("%d",&a[i]);

            b[i]=mx=max(mx,a[i]);

        }

        while(q--)

        {

            scanf("%d",&k);

            int l=lower_bound(b,b+n,k)-b;

            if(l==n){

                printf("are you ok\n");

                continue;

            }

            printf("%d\n",l);

            if(l==)continue;

            a[l-]++;

            b[l-]=max(a[l-],b[l-]);

        }

    }

}

巴特西

牛客网中南林业科技大学第十一届程序设计大赛J题二分+线段树

最新文章

热门文章

巴特西

牛客网 中南林业科技大学第十一届程序设计大赛J题 二分+线段树

最新文章

热门文章

牛客网中南林业科技大学第十一届程序设计大赛J题二分+线段树