P2801 教主的魔法

· · 题解

这道题乍一看，是区间修改+查询，以为是线段树，结果发现线段树做不了。

其实这道题就是一个分块。

分块的思想就是把整个数列分成sqrt(n)块，然后对每一块进行操作。

其中需要特别处理的，是左边和右边的一小段不在整块大区间内的部分。

具体看代码（自认为写得很短了）

代码如下（注释很详细的）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int bl, a[N], b[N], n, AD[1010];

void add(int l, int r, int w)
{
//左边一小块 
    int lp = min(r, (l / bl + 1) * bl - 1);//左边的一小块的右端点 
    for (int i = l; i <= lp; i++)
        a[i] += w;//这段小块区间直接加 
    for (int i = l/bl*bl; i < min((l/bl+1)*bl, n); i++)
        b[i] = a[i];//从这段小块区间复制下来排序 
    sort(b + (l/bl*bl), b + min((l/bl+1)*bl, n));//排序 
    if(lp == r)//如果是单点，跳过下面 
        return;
//右边一小块 
    int rp = r / bl * bl;//右边一小块的左端点 
    for (int i = rp; i <= r; i++)
        a[i] += w;//这段小块区间直接加 
    for (int i = rp; i < (r/bl+1)*bl; i++)
        b[i] = a[i];//这段小块区间复制下来排序 
    sort(b + rp, b + ((r/bl+1)*bl));//排序 
//处理中间整块的加 
    int t = (lp + 1) / bl;//整块的左端点 
    while(t * bl < rp)//整块整块的加，知道右端点 
        AD[t++] += w;//AD记录的是整块区间的加
}

int query(int l, int r, int w) 
{
    int ret = 0;
//左边一小块 
    int lp = min(r, (l / bl + 1) * bl - 1);//左边的一小块的右端点 
    for (int i = l; i <= lp; i++) 
        if(a[i] + AD[i/bl] >= w)//i/bl就是i所在的块 
            ret++;//>=w就累加 
    if(lp == r) //如果是单点，跳过下面 
        return ret;
//右边一小块 
    int rp = r / bl * bl;//右边一小块的左端点
    for (int i = rp; i <= r; i++) 
        if(a[i] + AD[i/bl] >= w)//i/bl就是i所在的块
            ret++;//>=w就累加 
//下面是处理中间的整块部分 
    int t = (lp+1) / bl;//整块的左端点 
    while(t * bl < rp) 
    {
        int L = t * bl, R = (t+1) * bl - 1;//l是一块的左端点，r是右端点 
        while(L < R)//因为每一块都是是排好序的，所以二分找到>=w的 
        {
            int Mid = (L + R) >> 1;//二分中间值 
            if(b[Mid] + AD[Mid/bl] >= w)//mid/bl就是mid所在的块
                R = Mid;//如果>=w的，左移 
            else L = Mid + 1;//否则右移 
        }
        ret += (t+1)*bl - R;//计算这段之间有多少个>=w的,即块的右端点-二分得到的断点 
        if(R == (t+1)*bl-1 && b[R] + AD[R/bl] < w)//如果整个块里面都没有>=w的 
            ret--;//减去包含了自己的1个 
        t++;//继续下一个块 
    }
    return ret;//返回有多少>=w的 
}

int main() {
    int Q, L, R, w;
    cin >> n >> Q;//n个数，Q个询问 
    for (int i = 0; i < n; i++) 
        cin >> a[i];//读入数列 
    bl = sqrt(n); //每一块的长度 
    for (int i = 0; i < n; i++)
        b[i] = a[i];//复制下来 
    for (int i = 0; i < n; i += bl)
        sort(b + i, b + min(i+bl, n)) ;//给每一块排序 
    char op[10];
    while(Q--)//询问 
    {
        scanf("%s%d%d%d", op, &L, &R, &w);
        L--; R--;//因为是从0开始的 
        if(op[0] == 'M')//区间加 
            add(L, R, w);
        else//区间查询 
            printf("%d\n", query(L, R, w));
    }
    return 0;
}