关于此题（教主的魔法）wa90的探讨

我这里用了个类lazytag的写法，关于二分我这里用的都是stl

hack数据都能过，但是最后一个点错了

数据

10 2
1 1 1 1 1 1 1 1 1 1
M 1 10 999
A 4 5 999

代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, arr[1001000], add[1001000], block, t, st[1000100], ed[1000100], pos[1001000], brr[1001000], q;
void build() {
    block = sqrt(n);
    t = n/block;
    if(n%block) ++t;
    for(int i=1; i<=t; ++i) {
        st[i] = (i-1)*block+1;
        ed[i] = i*block;
    }
    ed[t]=n;
    for(int i=1; i<=t; ++i) {
        sort(brr+st[i],brr+ed[i]+1);
    }
    for(int i=1; i<=n; ++i) {
        pos[i] = (i-1)/block+1;
    }
}
void Add(int L, int R, int W) {
    if(pos[L] == pos[R]) {
        int index = pos[L];
        for(int i=L; i<=R; ++i) {
            arr[i] = arr[i]+W;
        }
        for(int i=st[index]; i<=ed[index]; ++i) {
            brr[i] = arr[i];
        }
        sort(brr+st[index],brr+ed[index]+1);
        return;
    }
    else
    {
        int left = pos[L], right = pos[R];
        for(int i=L; i<=ed[left]; ++i) {
            arr[i] = arr[i]+W;
        }
        for(int i=st[left];i<=ed[left];++i) {
            brr[i] = arr[i];
        }
        sort(brr+st[left], brr+ed[left]+1);
        for(int i=left+1;i<right;++i) {
            add[i] += W;
        }
        for(int i=st[right]; i<=R; ++i) {
            arr[i] = arr[i]+W;
        }
        for(int i=st[right];i<=ed[right];++i) {
            brr[i] = arr[i];
        }
        sort(brr+st[right], brr+ed[right]+1);
    }
}
int que(int L, int R, int C) {
    if(pos[L] == pos[R]) {
        int sum = 0;
        for(int i=L; i<=R; ++i) {
            if(arr[i] >= C) {
                sum++;
            }
        }
        return sum;
    } else {
        int left = pos[L], right = pos[R], sum = 0, tempC;
        tempC = C-add[left];
        for(int i=L; i<=ed[left]; ++i) {
            if(arr[i] >= tempC) {
                sum++;
            }
        }
        for(int i=left+1; i<right; ++i) {
            tempC = C-add[i];
            int u = lower_bound(brr+st[i],brr+ed[i]+1,tempC)-brr;
            sum+=max(0ll, ed[i]-u+1);
        }
        tempC = C-add[right];
        for(int i=st[right]; i<=R; ++i) {
            if(arr[i] >= tempC) {
                sum++;
            }
        }
        return sum;
    }
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> q;
    for(int i=1; i<=n; ++i) {cin >> arr[i];brr[i]=arr[i];}
    build();
    for(int i=1; i<=q; ++i){
        char ch; cin >> ch;
        if(ch == 'M') {
            int L,R,W; cin >> L >> R >> W;
            Add(L,R,W);
        } else {
            int L,R,C; cin >> L >> R >> C;
            cout << que(L,R,C) << endl;
        }
    }
    return 0;
}