题解 P2801 【教主的魔法】

· · 题解

话说分块确实是一个非常好的算法，只可惜洛谷上的题目有点少。

看到这一题首先想到线段树，再发现线段树做不了，每个节点预处理出>=k的个数实在是太多了，

空间不能承受。

那么怎么用分块做呢？

先看看怎么查询块内>=k的个数的操作呢？

我们可以先将这个块排好序，然后二分查找k的值就好了。

至于两边不完整的块，暴力查询还没有排序的原本序列直接找就好了

再看看怎么修改？？

对于整块，我们可以打上一个add标记，这样二分查找就要查 >= k-add 的值。

对于不完整的块，我们暴力修改，再直接排序整个块就好了

然后就可以过了。

代码：

#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 感谢@多功能的荀彧

假数据害人啊