数列分块入门

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e4+5;
int n,len,cnt;
int a[MAXN],tag[MAXN];
int pos[MAXN],l[MAXN],r[MAXN];
inline void add(int x,int y,int k)
{
    if(x>y)return;
    if(pos[x]==pos[y])
    {
        for(register int i=x;i<=y;i++)
            a[i]+=k;
        return;
    }
    for(register int i=x;i<=r[pos[x]];i++)a[i]+=k;
    for(register int i=l[pos[y]];i<=y;i++)a[i]+=k;
    for(register int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
signed main()
{
    scanf("%lld",&n);
    len=sqrt(n);
    cnt=n/len+(n%len!=0);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        pos[i]=(i-1)/len+1;
    }
    for(register int i=1;i<=cnt;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    for(register int i=1;i<=n;i++)
    {
        int op,x,y,c;
        scanf("%lld%lld%lld%lld",&op,&x,&y,&c);
        if(op==0)add(x,y,c);
        if(op==1)printf("%lld\n",a[y]+tag[pos[y]]);
    }
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,len,cnt;
int a[MAXN],b[MAXN],tag[MAXN];
int pos[MAXN],l[MAXN],r[MAXN];
inline void add(int x,int y,int k)
{
    if(x>y)return;
    if(pos[x]==pos[y])
    {
        for(register int i=x;i<=y;i++)
            a[i]+=k;
        return;
    }
    for(register int i=x;i<=r[pos[x]];i++)a[i]+=k;
    for(register int i=l[pos[y]];i<=y;i++)a[i]+=k;
    for(register int i=pos[x]+1;i<=pos[y]-1;i++)tag[i]+=k;
}
inline int ask(int x,int y,int k)
{
    int sum=0;
    if(x>y)return 0;
    if(pos[x]==pos[y])
    {
        for(register int i=x;i<=y;i++)
            if(a[i]+tag[pos[i]]<k)sum++;
        return sum;
    }
    for(register int i=x;i<=r[pos[x]];i++)if(a[i]+tag[pos[i]]<k)sum++;
    for(register int i=l[pos[y]];i<=y;i++)if(a[i]+tag[pos[i]]<k)sum++;
    for(register int i=pos[x]+1;i<=pos[y]-1;i++)
    {
        int w=lower_bound(b+l[i],b+1+r[i],k-tag[i])-b;
        sum+=(w-l[i]);
    }
    return sum;
}
signed main()
{
    scanf("%lld",&n);
    len=sqrt(n);
    cnt=(n/len)+(n%len!=0);
    for(register int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        b[i]=a[i];
        pos[i]=(i-1)/len+1;
    }
    for(register int i=1;i<=cnt;i++)
    {
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    r[cnt]=n;
    for(register int i=1;i<=cnt;i++)
        sort(b+l[i],b+1+r[i]);
    for(register int i=1;i<=n;i++)
    {
        int op,x,y,c;
        scanf("%lld%lld%lld%lld",&op,&x,&y,&c);
        if(op==0)
        {
            add(x,y,c);
            for(register int i=l[pos[x]];i<=r[pos[x]];i++)b[i]=a[i];
            for(register int i=l[pos[y]];i<=r[pos[y]];i++)b[i]=a[i];
            sort(b+l[pos[x]],b+1+r[pos[x]]);
            sort(b+l[pos[y]],b+1+r[pos[y]]);
        }
        if(op==1)printf("%lld\n",ask(x,y,c*c));
    }
    return 0;
}