LOJ 数列分块入门 2
  • 板块学术版
  • 楼主Nodlek
  • 当前回复16
  • 已保存回复16
  • 发布时间2021/6/25 19:55
  • 上次更新2023/11/4 21:30:38
查看原帖
LOJ 数列分块入门 2
519187
Nodlek楼主2021/6/25 19:55

刚学分块,为什么这道题有初始化A不了,把初始化删掉就AC了?

//2021/6/25

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int ma=50005;

int l[ma],r[ma],pos[ma],a[ma],sum[ma],t[ma];

int n;

inline void Sort(int k)
{
    for(register int i=l[k];i<=r[k];i++)
    {
        t[i]=a[i];
    }

    sort(t+l[k],t+r[k]+1);
}

inline void modify(int le,int ri,int k)
{
    if(pos[le]==pos[ri])
    {
        for(register int i=le;i<=ri;i++)
        {
            a[i]+=k;
        }

        Sort(pos[le]);
    }

    else
    {
        for(register int i=le;i<=r[pos[le]];i++)
        {
            a[i]+=k;
        }

        for(register int i=l[pos[ri]];i<=ri;i++)
        {
            a[i]+=k;
        }

        Sort(pos[le]);

        Sort(pos[ri]);

        for(register int i=l[pos[le]]+1;i<=r[pos[ri]]-1;i++)
        {
            sum[i]+=k;
        }
    }
}

inline int query(int le,int ri,int k)
{
    int res=0;

    if(pos[le]==pos[ri])
    {
        for(register int i=le;i<=ri;i++)
        {
            if(a[i]+sum[i]<k)
            {
                res++;
            }
        }
    }

    else
    {
        for(register int i=le;i<=r[pos[le]];i++)
        {
            if(a[i]+sum[i]<k)
            {
                res++;
            }
        }

        for(register int i=l[pos[ri]];i<=ri;i++)
        {
            if(a[i]+sum[i]<k)
            {
                res++;
            }
        }

        for(register int i=l[pos[le]]+1;i<=r[pos[ri]]-1;i++)
        {
            int p=lower_bound(l[i]+t,r[i]+t+1,k-sum[i])-t-l[i];

            res+=p;
        }
    }
    
    return res;
}

int main(void)
{
	scanf("%d",&n);

    

    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(register int z=1;z<=n;z++)
    {
        int opt,le,ri,k;

        scanf("%d%d%d%d",&opt,&le,&ri,&k);

        if(opt==0)
        {
            modify(le,ri,k);
        }

        else
        {
            printf("%d\n",query(le,ri,k*k));
        }
    }

    return 0;
}
2021/6/25 19:55
加载中...