lyzqs的博客

分块入门题

对于每个块，拍个序

修改

对于一段区间[l,r]，中间完整的块直接打标记，两端暴力修改原数组就行

查询

对于一段区间[l,r]，中间的块内二分，两端暴力查询就好

然后就没了

#include <bits/stdc++.h>
#define il inline
#define Max 2000005
#define dg puts("qwq")
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
namespace lyzqs
{
    char In[Max],*ss=In,*tt=In;
    il int read()
    {
        char c=getchar();
        int x=0,f=1;
        while(c>'9'||c<'0')
        {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    int n,q,a[Max],b[Max],cnt,m;
    struct node
    {
        int l,r,tg;
    }c[2333];
    il void build()
    {
        int l=1;
        while(l<=n)
        {
            c[++cnt].l=l;
            c[cnt].r=min(n,l+m-1);
            sort(b+l,b+c[cnt].r+1);
            l+=m;
        }
    }
    il void mdf2(int id,int l,int r,int k)
    {
        for(int i=c[id].l;i<=c[id].r;i++)
        {
            b[i]=a[i]+c[id].tg;
            if(l<=i&&i<=r) b[i]+=k;
        }
        sort(b+c[id].l,b+c[id].r+1);
    }
    il void mdf(int l,int r,int k)
    {
        for(int i=1;i<=cnt;i++)
        {
            if(l<=c[i].l&&c[i].r<=r) c[i].tg+=k;
            else if(c[i].l<=l&&c[i].r<=r) mdf2(i,l,c[i].r,k);
            else if(r>=c[i].l&&r<=c[i].r) mdf2(i,c[i].l,r,k);
        }
    }
    il int find(int id,int k)
    {
        int l=c[id].l,r=c[id].r,pos=1e9;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(b[mid]+c[id].tg>=k) pos=mid,r=mid-1;
            else l=mid+1;
        }
        if(pos==1e9) return 0;
        else return c[id].r-pos+1;
    }
    il int qry2(int id,int l,int r,int k)
    {
        int res=0;
        for(int i=l;i<=r;i++)
        {
            if(a[id]+c[id].tg>=k) res++;
        }
        return res;
    }
    il int qry(int l,int r,int k)
    {
        int res=0;
        for(int i=1;i<=cnt;i++)
        {
            if(l<=c[i].l&&c[i].r<=r) res+=find(i,k);
            else if(c[i].l<=l&&c[i].r<=r) res+=qry2(i,l,c[i].r,k);
            else if(r>=c[i].l&&r<=c[i].r) res+=qry2(i,c[i].l,r,k);
        }
        return res;
    }
    void main()
    {
        n=read(),q=read();m=pow(n,0.5);
        for(int i=1;i<=n;i++) a[i]=b[i]=read();
        build();
        char opt;
        while(q--)
        {
            opt='!';
            while(opt!='M'&&opt!='A') opt=getchar();
            int x=read(),y=read(),z=read();
            if(opt=='M')
            {
                mdf(x,y,z);
            }
            else printf("%d\n",qry(x,y,z));
        }
    }
}
int main()
{
    lyzqs::main();
}