LibreOJ 6277. 数列分块入门 2

参考博客：https://blog.csdn.net/qq_36038511/article/details/79725027

这题我用分块来修改，用暴力查找也过了，但是感觉不应该这么笨的暴力查询，然后看了一下上面的博客，然后发现查找是也可以分块查找，但是要先排序，对于中间完整块可以在排完序的前提下用二分查找，对于不完整的块还是暴力查找。和上面的博客一样用了vector，感觉这样更简单一点，比较好区分块，虽然可能会慢点。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque> 
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 50005
/*struct point{
    int u,w;
};
bool operator <(const point &s1,const point &s2)
{
    if(s1.w!=s2.w)
    return s1.w>s2.w;
    else
    return s1.u>s2.u;
}*/
int n,m,k,t,block;
int a[maxn],tag[maxn],lump[maxn];
vector<int>ve[510];
void update(int x)
{
    ve[x].clear();//把第x块原来的值清除 
    for(int i=(x-1)*block+1;i<=min(x*block,n);i++)//这里要加min，因为第x块可能是最后一块并且是不完整的 
    ve[x].push_back(a[i]);//把增加了的值重新压入 
    sort(ve[x].begin(),ve[x].end());//排序 
}
void add(int l,int r,int c)
{
    for(int i=l;i<=min(lump[l]*block,r);i++)//暴力更新左边不完整的块 
    a[i]+=c;
    update(lump[l]);//更新值并且重新排序 
    if(lump[l]!=lump[r])
    {
        for(int i=(lump[r]-1)*block+1;i<=r;i++)//暴力更新右边不完整的块
        a[i]+=c;
        update(lump[r]);
    }
    for(int i=lump[l]+1;i<=lump[r]-1;i++)
    tag[i]+=c;
 } 
int find(int l,int r,int c)
{
    int ans=0;
    for(int i=l;i<=min(lump[l]*block,r);i++)//在左边不完整的块里查找 
    {
        if(a[i]+tag[lump[l]]<c)
        ans++;
    }
    if(lump[l]!=lump[r])
    {
        for(int i=(lump[r]-1)*block+1;i<=r;i++)//在右边的不完整的块里查找 
        {
            if(a[i]+tag[lump[r]]<c)
            ans++;
         } 
    }
    for(int i=lump[l]+1;i<=lump[r]-1;i++)//在中间的完整的并且有序的块里二分查找 
    {
        int t=c-tag[i];
        ans+=lower_bound(ve[i].begin(),ve[i].end(),t)-ve[i].begin();
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    
    fill(tag,tag+maxn-1,0);
    for(int i=0;i<=n;i++)
    ve[i].clear();
    block=sqrt(n);
    
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        lump[i]=(i-1)/block+1;
        ve[lump[i]].push_back(a[i]);
    }
    for(int i=1;i<=lump[n];i++)//把每一块的值进行排序 
    sort(ve[i].begin(),ve[i].end());
    
    for(int j=1;j<=n;j++)
    {
        int op,l,r,c;
        scanf("%d%d%d%d",&op,&l,&r,&c);
        if(op==0)
        add(l,r,c);
        else
        {
            int ans=find(l,r,c*c);
            printf("%d
",ans);
        }
    }
    return 0;
}