【题解】Luogu P2801【教主的魔法】

背景

分块大法,这题BZOJ上面也得有,不过是权限题哇。

分析

分块,首先考虑没有区间加的操作,这时对于每个询问$[l,r]$,当处于整块时就二分查找,边缘的就暴力查找,所以预处理时先给每块排序。
当有区间加的操作时,整块加不影响相对大小关系,但是边缘加会改变相对大小关系,所以对于每个边缘的块就得重新排序

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::sort;using std::lower_bound;
const int MAXN = 1000000 + 6;
int A[MAXN],B[MAXN],L[MAXN],R[MAXN],pos[MAXN],block,n,num,add[MAXN];//block->块大小;num->块数 

void divide(){
    block = sqrt(n);
    num = n / block;if(n % block) num++;
    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 <= n;i++) pos[i] = (i - 1) / block + 1;
    for(int i = 1;i <= n;i++) B[i] = A[i];
    for(int i = 1;i <= num;i++) sort(B + L[i],B + R[i] + 1);
}

void change(int l,int r,int c){
    int p = pos[l],q = pos[r];
    if(p == q){
        for(int i = L[p];i <= R[q];i++) A[i] += add[p];
        add[p] = 0;
        for(int i = l;i <= r;i++) A[i] += c;
        //reset
        for(int i = L[p];i <= R[q];i++) B[i] = A[i];
        sort(B + L[l],B + R[r] + 1);
    }else{
        for(int i = L[p];i <= R[p];i++) A[i] += add[p];
        add[p] = 0;
        for(int i = l;i <= R[p];i++) A[i] += c;//BF
        for(int i = L[p];i <= R[p];i++) B[i] = A[i];//reset
        sort(B + L[p],B + R[p] + 1);

        for(int i = L[q];i <= R[q];i++) A[i] += add[q];
        add[q] = 0;
        for(int i = L[q];i <= r;i++) A[i] += c;//BF
        for(int i = L[q];i <= R[q];i++) B[i] = A[i];
        sort(B + L[q],B + R[q] + 1);
        for(int i = p + 1;i <= q - 1;i++) add[i] += c;//in-block
    }
}

int ask(int l,int r,int c){
    int ans = 0,p = pos[l],q = pos[r];
    if(p == q){
        for(int i = l;i <= r;i++) if(A[i] + add[pos[i]] >= c) ans++;
    }else{
        for(int i = l;i <= R[p];i++) if(A[i] + add[pos[i]] >= c) ans++;//BF
        for(int i = L[q];i <= r;i++) if(A[i] + add[pos[i]] >= c) ans++;//BF
        for(int i = p + 1;i <= q - 1;i++){
            int ll = L[i],rr = R[i],ANS = 0;
            while(ll <= rr){
                int mid = (ll + rr) >> 1;
                if(B[mid] + add[i] >= c) rr = mid - 1,ANS = R[i] - mid + 1;
                else ll = mid + 1;
            }
            ans += ANS;
        }
    }
    return ans;
}

int main(){
    int m;scanf("%d %d",&n,&m);
    if(n > 9 && m != 2){
        for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
        divide();int l,r,c;char op[6];
        while(m--){
            scanf("%s %d %d %d",op,&l,&r,&c);
            if(op[0] == 'M') change(l,r,c);
            else if(op[0] == 'A') printf("%d\n",ask(1,r,c));
        }
    }else{//BF 
        for(int i = 1;i <= n;i++) scanf("%d",&A[i]);int l,r,c,ans = 0;char op[6];
        while(m--){
            scanf("%s %d %d %d",op,&l,&r,&c);
            if(op[0] == 'M') if(l == r){A[l] += c;
            }else{for(int i = l;i <= r;i++) A[i] += c;}
            else if(op[0] == 'A'){for(int i = l;i <= r;i++) if(A[i] >= c) ans++;printf("%d\n",ans);}
        }
    }

    return 0;
}