【分块】[LUOGU 教主的魔法] 分块模板

本文主要是介绍【分块】[LUOGU 教主的魔法] 分块模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题目链接：[LUOGU 教主的魔法]
题解：
（才发现我的分块再洛谷上交的题比较少都是在别的OJ上写的比较多，所以就打算补补。。。）
这个题就是个分块的模板题，，，，

这里还是也要补充一下数组和vector的比较：
vector：不定长的数组，但是是动态的，相对于数组来说会比较慢（毕竟是STL），但是比较好排序，以及比较由于是不定长的所以就不用管它的长度。
数组：比较固定是静态的，由于是c++自带的所以就比较简洁而且比较快，但是需要范围的固定。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e6+7;
int n,m,block,num,a[sea],b[sea],belong[sea],l[sea],r[sea],lazy[sea];
void reset(int x){for(int i=l[x];i<=min(n,r[x]);i++) b[i]=a[i];sort(b+l[x],b+r[x]+1);}//这一点=我之前是用vector写的，但是竟然反复TLE所以就改成了数组，，
int find(int x,int z)
{int L=(x-1)*block+1,R=min(x*block,n);int last=R;while(L<=R){int mid=(L+R)>>1;if(b[mid]<z)L=mid+1; else R=mid-1;}return last-L+1;
}
void build()
{block=sqrt(n); num=n/block;if(n%block) num++; for(int i=1;i<=n;i++) a[i]=read(),belong[i]=(i-1)/block+1,b[i]=a[i];for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block; r[num]=n;for(int i=1;i<num;i++) reset(i);
}
void alter(int x,int y,int z)
{for(int i=x;i<=min(r[belong[x]],y);i++) a[i]+=z;if(belong[x]!=belong[y]){for(int i=l[belong[y]];i<=y;i++) a[i]+=z; for(int i=belong[x]+1;i<belong[y];i++) lazy[i]+=z;	} reset(belong[x]);reset(belong[y]);
}
int ask(int x,int y,int z)
{int ans=0;for(int i=x;i<=min(r[belong[x]],y);i++) if(a[i]+lazy[belong[x]]>=z) ans++;if(belong[x]!=belong[y]){for(int i=l[belong[y]];i<=y;i++) if(a[i]+lazy[belong[y]]>=z) ans++;for(int i=belong[x]+1;i<belong[y];i++) ans+=find(i,z-lazy[i]); //这点原来尝试着用lower_bound()，但是好像不是很对，，而且改完之后就WA掉了，比较不想搞了，就直接手写了，，，} return ans;
}
int main()
{n=read(); m=read(); build();for(int i=1;i<=m;i++){char ch[5];scanf("%s",ch); int x=read(),y=read(),z=read();if(ch[0]=='M') alter(x,y,z);else printf("%d\n",ask(x,y,z));}return 0;
}