教主的魔法

分块法

这道题目是一个典型的区间更新和区间查询问题。具体来说，我们需要支持两种操作：

区间加法：将区间 $[L, R]$ 内所有元素的值加上 $W$ 。
区间计数查询：统计区间 $[L, R]$ 内有多少个元素的值大于等于 $C$ 。

我们需要结合题目的数据范围来选择合适的算法。数据范围： $N \le 10^6$ ， $Q \le 3000$ 。

算法分析

1. 暴力法

对于修改操作 M L R W，遍历区间 $[L, R]$ ，将每个元素加上 $W$ 。时间复杂度 $O(N)$ 。
对于查询操作 A L R C，遍历区间 $[L, R]$ ，统计大于等于 $C$ 的元素个数。时间复杂度 $O(N)$ 。
总时间复杂度为 $O(N \times Q)$ 。代入最大数据， $10^6 \times 3000 = 3 \times 10^9$ ，这远远超出了通常 1 秒钟约 $10^8$ 次运算的时间限制，因此暴力法不可行。

2. 线段树 标准的线段树擅长处理区间求和、区间最值等问题。对于“区间内大于等于 $C$ 的个数”这类值域相关的查询，标准的线段树并不适用。虽然可以用线段树套平衡树或者归并树来解决，但这类数据结构非常复杂，且在区间修改的情况下维护起来更加困难。

3. 分块算法 (Square Root Decomposition) 分块算法是解决此类问题的常用且有效的方法，特别是在结合了数据范围的特点后。这道题目的特点是 $N$ 很大，但 $Q$ 相对较小。分块算法可以在 $O(Q\sqrt{N} \log N)$ 或 $O(Q\sqrt{N})$ 的时间复杂度内解决问题，这在当前数据范围内是可接受的。

分块算法思路

我们将 $N$ 个英雄分成若干个块，每块的大小约为 $\sqrt{N}$ 。总共大约有 $\sqrt{N}$ 个块。

数据结构设计：

a[N]: 存储英雄当前的真实身高（或者基础身高）。
block[K]: 一个向量数组（Vector Array），block[i] 存储第 $i$ 个块内所有英雄身高的排序后的副本。用于快速进行二分查找。
lazy[K]: 懒标记数组，lazy[i] 记录第 $i$ 个块整体被增加了多少身高。
bel[N]: 记录第 $i$ 个英雄属于哪个块。

块的大小 $S$ 通常取 $\sqrt{N \log N}$ 或直接取 $\sqrt{N}$ 。在这道题中， $N=10^6$ ，取 $S=1000$ 比较合适。

初始化： 读取初始身高，填充 a 数组，并将数据同步到对应的 block 向量中。然后对每个 block 向量进行排序。时间复杂度 $O(N \log N)$ 。

修改操作 M L R W： 区间 $[L, R]$ 可能跨越多个块。由于 $N$ 很大， $R-L$ 可能很大，我们不能暴力更新所有元素。

处理左端不完整的块：对于 $L$ 所在的块，如果它只被覆盖了一部分，我们暴力更新原数组 a 中对应的元素，并在更新后重新排序该块对应的 block 向量。
处理中间完整的块：对于 $[L, R]$ 覆盖的中间那些完整的块，我们只需要修改它们的懒标记 lazy 即可，即 lazy[i] += W。不需要动 a 和 block。
处理右端不完整的块：同左端一样，暴力更新原数组 a 并重新排序对应的 block 向量。

复杂度分析：两端不完整的块最多包含 $2S$ 个元素，排序需要 $O(S \log S)$ 。中间完整的块最多有 $N/S$ 个，更新懒标记需要 $O(N/S)$ 。如果 $S=\sqrt{N}$ ，单次修改复杂度为 $O(\sqrt{N} \log N)$ 。

查询操作 A L R C： 同样，查询区间可能跨越多个块。

处理左端不完整的块：遍历该块中属于 $[L, R]$ 范围的元素，检查 a[i] + lazy[bel[i]] >= C 是否成立，统计个数。
处理中间完整的块：对于每个完整的块 $i$ ，我们利用已经排序好的 block[i] 向量。我们需要找出有多少个元素 $x$ 满足 $x + lazy[i] \ge C$ ，即 $x \ge C - lazy[i]$ 。这可以通过在 block[i] 上进行二分查找（lower_bound 函数）快速实现。
处理右端不完整的块：同左端一样，暴力遍历统计。

复杂度分析：两端暴力遍历最多 $O(S)$ 。中间完整块最多 $N/S$ 个，每个进行二分查找 $O(\log S)$ 。总复杂度 $O(S + \frac{N}{S}\log S)$ 。如果 $S=\sqrt{N}$ ，单次查询复杂度为 $O(\sqrt{N} \log N)$ 。

总复杂度： 总时间复杂度为 $O(N \log N + Q\sqrt{N} \log N)$ 。代入数据， $N=10^6, Q=3000, \sqrt{N}=1000, \log N \approx 20$ 。大约计算量在 $3000 \times 1000 \times 20 = 6 \times 10^7$ 级别，可以通过此题。

总结

鉴于题目 $N$ 大 $Q$ 小的数据特点以及需要支持区间加和区间值域计数的操作，分块算法 (Square Root Decomposition) 是解决这道题的最佳选择。它通过维护块内的有序结构和块间的懒标记，平衡了修改和查询的复杂度。

数据特征的暗示再来看一眼极其特殊的数据范围： $N \le 10^6$ (非常大) $Q \le 3000$ (非常小)这种 $N$ 极大而 $Q$ 极小的数据分布，通常强烈暗示两种解法：

分块算法：复杂度通常与 $Q\sqrt{N}$ 相关。某些暴力优化或特定树形结构：
如果不带持久化，使用“线段树套平衡树（Treap）”或者“归并树（Merge Sort Tree）+ 分块特定优化”也许能在 $O(Q \log^2 N)$ 或类似复杂度内通过。为什么分块是首选？在 $N=10^6, Q=3000$ 的情况下，分块算法 $O(Q\sqrt{N} \log N)$ 的常数较小，实现相对简单，是处理这种“区间修改 + 区间特定值查询”最稳健的方法。

代码

cpp

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int maxn =  2e6+5;
typedef long long ll;
ll n,m;
ll a[maxn];


// ---- block
struct Block {
    ll block;
    ll t;
    ll pos[maxn];
    ll st[maxn];
    ll ed[maxn];

    // ll sum[maxn];
    ll addflag[maxn];
    const int maxn_block = 2005;
    vector<ll> sorted_blocks[2005]; // 新增：存储每个块排序后的副本

    void init(){
        block = sqrt(n);
        t = n / block;
        if( n % block) t++;
        for(ll i = 1;i <= t ;++i ) // i: 1->t
        {
            st[i] = (i-1) * block + 1;
            ed[i] = i * block;
        }
        ed[t] = n; // 修正最后一个快的结尾
        for(ll i = 1;i <= n ;++i ) // i: 1->n
        {
            pos[i] = (i-1) / block + 1;
        }

        // 初始化 sorted_blocks
        for (ll i = 1; i <= t; ++i) {
            addflag[i] = 0; // 初始化懒标记
            sorted_blocks[i].clear();
            for (ll j = st[i]; j <= ed[i]; ++j) {
                sorted_blocks[i].push_back(a[j]);
            }
            std::sort(sorted_blocks[i].begin(), sorted_blocks[i].end());
        }

        // for(ll i = 1;i <= t ;++i ) // i: 1->t
        // {
        //     for(ll j = st[i];j <= ed[i] ;++j ) // j: 1->n
        //     {
        //         sum[i] += a[j];
        //     }
        // }
    }
    
    // 辅助函数：重建并排序指定块
    void reset_block(int b) {
        sorted_blocks[b].clear();
        for (ll i = st[b]; i <= ed[b]; ++i) {
            sorted_blocks[b].push_back(a[i]);
        }
        std::sort(sorted_blocks[b].begin(), sorted_blocks[b].end());
    }

    //区间修改 
    void update(ll L,ll R,ll d) {
        ll p = pos[L],q = pos[R];
        if( p == q) {
            for(ll i = L;i <= R;i++) {
                a[i] +=d;
            }
            // std::sort(a+st[p],a+ed[p]+1); //重新排序
            reset_block(p);
        }
        else {
            for(ll i = p+1;i <= q-1;i++) 
                addflag[i] += d;
            for(ll i = L; i <= ed[p] ;i++) {
                a[i] += d;
            }
            for(ll i = st[q];i <= R;i++) {
                a[i] += d;
            }
            reset_block(p);
            reset_block(q);
        }
    }

    long long query(ll L,ll R,ll val) {
        long long ret = 0;
        ll p = pos[L], q = pos[R];
        if( p == q) {
            for(ll i = L;i <= R;i++) {
                if( a[i] + addflag[p] >= val) ++ret;
            }
        }
        else {
            for(ll i = p+1;i<=q-1;i++) {
                // a[i] + flag >= c
                // a[i] >= c- flag
                ll new_val = val-addflag[i];
                // 在排序后的 vector 上进行二分查找
                std::vector<ll>::iterator it = lower_bound(sorted_blocks[i].begin(), sorted_blocks[i].end(), new_val);
                ret += (sorted_blocks[i].end() - it);
            }
            for(ll i = L; i <= ed[p] ;i++) {
                if( a[i] + addflag[p] >= val) ++ret;
            }
            for(ll i = st[q];i <= R;i++) {
                if( a[i] + addflag[q] >= val) ++ret;
            }
        }
        return ret;
    }
} myblock;

void init() {
    std::cin >> n >> m;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }
}


int main() {
    init();
    myblock.init();
    for(int i = 1;i <= m ;++i ) // i: 1->n
    {
        char opt;
        int x,y;
        int key;
        std::cin >> opt >> x >> y;
        std::cin >> key;
        if( opt == 'M') {
            myblock.update(x,y,key);
        }
        else {
            cout << myblock.query(x, y,key) << endl;
        }
        
    }
    

    return 0;
}

目录

分块法

算法分析

分块算法思路

总结

代码