RT,题目链接

code

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+5;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void print(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) print(x/10);
     putchar(x%10+'0');
}
int size;int belong[maxn],a[maxn],taga[maxn];
vector<int>s[505];
int n;
inline void reconstruct(int pos)
{
    s[pos].clear();
    for(int i=(pos-1)*size+1;i<=min(size*pos,n);i++)s[pos].push_back(a[i]);
    sort(s[pos].begin(),s[pos].end());
}
inline void add(int l,int r,int k)
{
    for(int i=l;i<=min(belong[l]*size,r);i++)a[i]+=k;
    reconstruct(belong[l]);
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*size+1;i<=r;i++)a[i]+=k;
        reconstruct(belong[r]);
    }
    for(int i=belong[l]+1;i<=belong[r]-1;i++)taga[i]+=k;
}
inline int search(int l,int r,int k)
{
    int ans=0;
    for(int i=l;i<=min(belong[l]*size,r);i++)if(a[i]+taga[belong[a[i]]]<k)ans++;
    if(belong[l]!=belong[r])
    {
        for(int i=(belong[r]-1)*size+1;i<=r;i++)if(a[i]+taga[belong[a[i]]]<k)ans++;
    }
    for(int i=belong[l]+1;i<=belong[r]-1;i++)
    {
        int x=k-taga[i];
        ans+=lower_bound(s[i].begin(),s[i].end(),x)-s[i].begin();
    }
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    size=sqrt(n);
    for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1,s[belong[i]].push_back(a[i]);
    for(int i=1;i<=belong[n];i++)sort(s[i].begin(),s[i].end());
    for(int i=1;i<=n;i++)
    {
        int cz,l,r,k;
        cz=read();l=read();r=read();k=read();
        if(cz==0)add(l,r,k);
        if(cz==1)print(search(l,r,k*k)),putchar('\n');
    } 
    //system("pause");
    return 0;
}