题解 P2801 【教主的魔法】
Jianuo_Zhu
2017-11-28 23:13:02
话说分块确实是一个非常好的算法，只可惜洛谷上的题目有点少。
看到这一题首先想到线段树，再发现线段树做不了，每个节点预处理出>=k的个数实在是太多了，
空间不能承受。
那么怎么用分块做呢？
先看看怎么查询块内>=k的个数的操作呢？
我们可以先将这个块排好序，然后二分查找k的值就好了。
至于两边不完整的块，暴力查询还没有排序的原本序列直接找就好了
再看看怎么修改？？
对于整块，我们可以打上一个add标记，这样二分查找就要查 >= k-add 的值。
对于不完整的块，我们暴力修改，再直接排序整个块就好了
然后就可以过了。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=1e6+10;
int n,q,a[maxn],b[maxn],l[maxn],r[maxn],belong[maxn],add[maxn],block,num;
void build(void);
void update(int ll,int rr,int w);
int ask(int ll,int rr,int w);
int find(int x,int w);
void reset(int x){
for(int i=l[belong[x]]; i<=r[belong[x]]; i++) b[i] = a[i];
sort(b+l[belong[x]],b+r[belong[x]]+1);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build();
int x,y,w;
for(int i=1;i<=q;i++){
char c[5];
scanf("%s%d%d%d",c,&x,&y,&w);
if(c[0]=='M') update(x,y,w);
else printf("%d\n",ask(x,y,w));
}
return 0;
}
void build(void){
block=sqrt(n);
num=n/block;if(n%block) num++;
for(int i=1;i<=n;i++)
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++)
sort(b+l[i],b+r[i]+1);
return;
}
void update(int ll,int rr,int w){
if(belong[ll]==belong[rr]){
for(int i=ll;i<=rr;i++)
a[i]+=w;
reset(ll);return;
}
for(int i=ll;i<=r[belong[ll]];i++){
a[i]+=w;
}
for(int i=l[belong[rr]];i<=rr;i++){
a[i]+=w;
}
reset(ll);reset(rr);
for(int i=belong[ll]+1;i<belong[rr];i++)
add[i]+=w;
}
int ask(int ll,int rr,int w){
int cnt=0;
if(belong[ll]==belong[rr]){
for(int i=ll;i<=rr;i++)
if(a[i] + add[belong[ll]]>=w)cnt++;
return cnt;
}
for(int i=ll;i<=r[belong[ll]];i++)
if(a[i] + add[belong[i]]>=w) cnt++;
for(int i=l[belong[rr]];i<=rr;i++)
if(a[i] + add[belong[i]]>=w) cnt++;
for(int i=belong[ll]+1;i<belong[rr];i++)
cnt+=find(i,w-add[i]);
return cnt;
}
int find(int x,int w){
int ll=l[x],rr=r[x],mid;
while(ll<=rr){
mid=(ll+rr)/2;
if(b[mid]<w) ll=mid+1;
else rr=mid-1;
}
return r[x]-ll+1;
}
```
更新：2018-3-5
原本代码中有一处错误，详情请见https://www.luogu.org/discuss/show/31449
感谢@Sooke
更新：2018-3-25 又被大佬们发现错误，详情还是请见https://www.luogu.org/discuss/show/31449
感谢@多功能的荀彧
~~假数据害人啊~~