LOJ#6280. 数列分块入门 4

感觉这个不算科技吧，就是现在把操作降在块内了，算是暴力的优化

LOJ6277. 数列分块入门 1

对于这些数你有两种操作，0是区间+，1是区间查询

#include
     
      using namespace std;#define N 50005int m,belong[N];int a[N],tag[N];void change(int l,int r,int val){    for(int i=l;i<=min(r,belong[l]*m);i++) a[i]+=val;//将a块内剩余部分暴力更新    if(belong[l]!=belong[r])    {        for(int i=(belong[r]-1)*m+1;i<=r;i++) a[i]+=val;//将b块内剩余部分暴力更新    }    for(int i=belong[l]+1;i<=belong[r]-1;i++)tag[i]+=val;//将整块需要加的值更新上去}int main(){    int n;    scanf("%d",&n);    m=sqrt(n);//一块有几个    for(int i=1;i<=n;i++) belong[i]=(i-1)/m+1;//将每个值分到所给的块内    for(int i=1;i<=n;i++) scanf("%d",&a[i]);    for(int i=1,op,l,r,val;i<=n;i++)    {        scanf("%d%d%d%d",&op,&l,&r,&val);        if(!op)change(l,r,val);        else printf("%d\n",tag[belong[r]]+a[r]);//tag获取这个序列被加的值    }    return 0;}
     

LOJ6278. 数列分块入门 2

这个还是区间加，但是要查询区间小于c*c的值

这个就麻烦多了，还要排序的啊

#include
     
      using namespace std;#define N 50005int n,m,belong[N];int a[N],tag[N];vector
      
       vec[N];void reset(int x){    //将两个特殊的块更新    vec[x].clear();    for(int i=(x-1)*m+1; i<=min(x*m,n); i++)vec[x].push_back(a[i]);    sort(vec[x].begin(),vec[x].end());}void change(int l,int r,int val){    for(int i=l; i<=min(r,belong[l]*m); i++) a[i]+=val; //将a块内剩余部分暴力更新    reset(belong[l]);    if(belong[l]!=belong[r])    {        for(int i=(belong[r]-1)*m+1; i<=r; i++) a[i]+=val; //将b块内剩余部分暴力更新        reset(belong[r]);    }    for(int i=belong[l]+1; i<=belong[r]-1; i++)tag[i]+=val; //将整块需要加的值更新上去}int query(int l,int r,int val){    int ans=0;    for(int i=l; i<=min(belong[l]*m,r); i++)if(a[i]+tag[belong[l]]
      
     

 

LOJ6279. 数列分块入门 3

询问区间内小于某个值 x的前驱（比其小的最大元素）

这个上面改改就行了

#include
     
      using namespace std;#define N 100005int n,m,belong[N];int a[N],tag[N];vector
      
       vec[N];void reset(int x){    //将两个特殊的块更新    vec[x].clear();    for(int i=(x-1)*m+1; i<=min(x*m,n); i++)vec[x].push_back(a[i]);    sort(vec[x].begin(),vec[x].end());}void change(int l,int r,int val){    for(int i=l; i<=min(r,belong[l]*m); i++) a[i]+=val; //将a块内剩余部分暴力更新    reset(belong[l]);    if(belong[l]!=belong[r])    {        for(int i=(belong[r]-1)*m+1; i<=r; i++) a[i]+=val; //将b块内剩余部分暴力更新        reset(belong[r]);    }    for(int i=belong[l]+1; i<=belong[r]-1; i++)tag[i]+=val; //将整块需要加的值更新上去}int query(int l,int r,int val){    int ans=-1;    for(int i=l; i<=min(belong[l]*m,r); i++)if(a[i]+tag[belong[l]]
       
        =1) ans=max(ans,vec[i][pos-1]+tag[i]);    }    return ans;}int main(){    scanf("%d",&n);    m=sqrt(n);//一块有几个    for(int i=1; i<=n; i++)belong[i]=(i-1)/m+1; //将每个值分到所给的块内    for(int i=1; i<=n; i++)scanf("%d",&a[i]),vec[belong[i]].push_back(a[i]);    for(int i=1;i<=belong[n];i++)sort(vec[i].begin(),vec[i].end());//每块要先保证有序，因为以后不更新了    for(int i=1,op,l,r,val; i<=n; i++)    {        scanf("%d%d%d%d",&op,&l,&r,&val);        if(!op)change(l,r,val);        else printf("%d\n",query(l,r,val));    }    return 0;}
       
      
     

 当然也可以用set去维护这个块，那个lowwerbound不要用错

#include
     
      #include
      
       using namespace std;#define N 100005int n,m,belong[N];int a[N],tag[N];set
       
        S[N];void change(int l,int r,int val){    for(int i=l; i<=min(r,belong[l]*m); i++)    {        S[belong[l]].erase(a[i]);        a[i]+=val; //将a块内剩余部分暴力更新        S[belong[l]].insert(a[i]);    }    if(belong[l]!=belong[r])    {        for(int i=(belong[r]-1)*m+1; i<=r; i++)        {            S[belong[r]].erase(a[i]);            a[i]+=val; //将b块内剩余部分暴力更新            S[belong[r]].insert(a[i]);        }    }    for(int i=belong[l]+1; i<=belong[r]-1; i++)tag[i]+=val; //将整块需要加的值更新上去}int query(int l,int r,int val){    int ans=-1;    for(int i=l; i<=min(belong[l]*m,r); i++)if(a[i]+tag[belong[l]]
        

::iterator it=S[i].lower_bound(val-tag[i]);//小于等于 if(it!=S[i].begin())ans=max(ans,*(--it)+tag[i]); } return ans;}int main(){ scanf("%d",&n); m=sqrt(n+0.5);//一块有几个 for(int i=1; i<=n; i++)belong[i]=(i-1)/m+1; //将每个值分到所给的块内 for(int i=1; i<=n; i++)scanf("%d",&a[i]),S[belong[i]].insert(a[i]); for(int i=1,op,l,r,val; i<=n; i++) { scanf("%d%d%d%d",&op,&l,&r,&val); if(!op)change(l,r,val); else printf("%d\n",query(l,r,val)); } return 0;}