教主的魔法
题目描述
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。
输入输出格式
输入格式：
第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
第2行有N个正整数，第i个数代表第i个英雄的身高。
第3到第Q+2行每行有一个操作：
（1） 若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2） 若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。
输出格式：
对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。
输入输出样例
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4
2
3
说明
【输入输出样例说明】
原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。
【数据范围】
对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。
分析：
一道练习数列分块的好题。
分析一下就能发现线段树无法处理此题的询问。这里采用数列分块的方法做。
记录两个数组，一个记录原数列，一个在原数列的基础上对每一个块内的元素进行排序，这样可以方便查找答案。
修改的时候只要给每一块打上标记就行了，不过要注意，左右两端可能会有多出来的部分需要暴力修改。然后查询时先把左右两端多出的部分暴力求出，然后在中间的每一个块内二分答案找到大于询问值的元素个数。
另外注意特判修改和询问的左右端点在同一个块内的情况。
Code：
//It is made by HolseLee on 7th Sep 2018
//Luogu.org P2801
#include<bits/stdc++.h>
using namespace std; const int N=1e6+;
int n,m,tot,siz,be[N],l[],r[],sign[],a[N],b[N]; inline int read()
{
char ch=getchar(); int num=; bool flag=false;
while( ch<'' || ch>'' ) {
if( ch=='-' ) flag=true;
ch=getchar();
}
while( ch>='' && ch<='' ) {
num=num*+ch-'';
ch=getchar();
}
return flag ? -num : num;
} inline void reset(int x)
{
for(int i=l[x]; i<=r[x]; ++i) b[i]=a[i];
sort(b+l[x],b+r[x]+);
} void ready()
{
siz=sqrt(n); tot=n/siz; n%siz ? tot++ : ;
for(int i=; i<=n; ++i) be[i]=(i-)/siz+;
for(int i=; i<=tot; ++i) {
l[i]=(i-)*siz+; r[i]=i*siz;
}
r[tot]=n;
for(int i=; i<=tot; ++i)
sort(b+l[i],b+r[i]+);
} inline void update(int x,int y,int v)
{
if( be[x]==be[y] ) {
for(int i=x; i<=y; ++i) {
a[i]+=v; b[i]=a[i];
}
reset(be[x]); return;
}
for(int i=x; i<=r[be[x]]; ++i) {
a[i]+=v; b[i]=a[i];
} reset(be[x]);
for(int i=l[be[y]]; i<=y; ++i) {
a[i]+=v; b[i]=a[i];
} reset(be[y]);
for(int i=be[x]+; i<be[y]; ++i) {
sign[i]+=v;
}
} inline int find(int x,int v)
{
int L=l[x],R=r[x],mid;
while( L<=R ) {
mid=(L+R)>>;
if( b[mid]+sign[x]<v ) L=mid+;
else R=mid-;
}
return r[x]-L+;
} inline int quary(int x,int y,int v)
{
int ret=;
if( be[x]==be[y] ) {
for(int i=x; i<=y; ++i) {
ret+=(a[i]+sign[be[i]]>=v);
}
return ret;
}
for(int i=x; i<=r[be[x]]; ++i) ret+=(a[i]+sign[be[i]]>=v);
for(int i=l[be[y]]; i<=y; ++i) ret+=(a[i]+sign[be[i]]>=v);
for(int i=be[x]+; i<be[y]; ++i) ret+=find(i,v);
return ret;
} int main()
{
n=read(); m=read();
for(int i=; i<=n; ++i) a[i]=read(), b[i]=a[i];
ready();
char opt[]; int x,y,z;
for(int i=; i<=m; ++i) {
scanf("%s",opt);
x=read(), y=read(), z=read();
if( opt[]=='A' ) printf("%d\n",quary(x,y,z));
else update(x,y,z);
}
return ;
}