一. 洛谷P2801_教主的魔法

二. 思路

• 若每个块内有序, 我们可以利用二分，logn算出这个块对答案的贡献
• 所以对每个块, 多维护一个s数组，里面是当前块内的所有值的有序数组
• 对于修改操作，不完整的块直接暴力判断，然后排序对s数组，根号n*logn
• 完整的块直接累加懒标记, 显然整块加并不会改变，块内数的相对关系
• 对于询问操作，不完整部分直接暴力询问
• 完整部分，直接二分s，的处贡献, 根号n*logn
• 综上总的复杂度为m*$\sqrt{n}$*$\log{$\sqrt{n}$}$

三. 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
namespace Question
{
    const int N=1e6+10, M=1e3+10;

    int n, q;
    int a[N];
}
using namespace Question;

namespace Chunked
{
    int len;//每块长度
    int belong[N];//每个值属于哪个块
    struct Block
    {
        int l, r;//每段的起点和终点
        int add, cnt;//懒标记, 块大小
        int s[M];//每块含有哪些值, 是有序数组, 下标从1开始
    }block[M];
    
    void init()//初始化函数
    {
        len=max(1, (int)sqrt(n));
        for(int i=1;i<=n;i++)//块号从0开始
        {
            int id=(i-1)/len;//wa点, 注意实际下标映射到的块
            belong[i]=id;//最后一个块长度可能不足len
            block[id]={id*len+1, min(n, id*len+len), 0};//下标从1开始
        }
        
        for(int i=belong[1];i<=belong[n];i++)
        {
            int k=0;
            auto &b=block[i];
            for(int j=block[i].l;j<=block[i].r;j++)
                b.s[k++]=a[j];
            b.cnt=k;
            sort(b.s, b.s+b.cnt);//wa点, 排序要用实际块长
        }
    }
    
    int query(int l, int r, int x)//询问[l,r]内>=x的数的个数
    {
        int ans=0;
        if(belong[l]==belong[r])//l, r在同一块内
        {
            for(int i=l;i<=r;i++)
                if(a[i]+block[belong[i]].add>=x)
                    ans++;
        }
        else
        {
            int i=l, j=r;
            while(belong[l]==belong[i])
            {
                if(a[i]+block[belong[i]].add>=x)
                    ans++;
                i++;
            }
                
            while(belong[r]==belong[j])
            {
                if(a[j]+block[belong[j]].add>=x)
                    ans++;
                j--;
            }
                
            for(int k=belong[i];k<=belong[j];k++)
            {
                auto &b=block[k];
                auto index=lower_bound(b.s, b.s+b.cnt, x-block[k].add);//得到实际下标
                ans+=b.cnt-(index-b.s);//算出贡献
            }
        }
        
        return ans;
    }
    
    int getId(Block b, int x)//得到某个要修改的值原来在s数组的下标
    {
        return lower_bound(b.s, b.s+b.cnt, x)-b.s;
    }
    
    void modify(int l, int r, int x)//给[l,r]区间每个数加上x
    {
        if(belong[l]==belong[r])//l, r在同一块内
        {
            auto &b=block[belong[l]];
            for(int i=l;i<=r;i++)
            {
                int id=getId(b, a[i]);
                a[i]+=x, b.s[id]=a[i];
            }
            sort(b.s, b.s+b.cnt);
        }
        else
        {
            int i=l, j=r;
            auto &b=block[belong[l]];
            while(belong[l]==belong[i])//处理左右两边
            {
                int id=getId(b, a[i]);
                a[i]+=x, b.s[id]=a[i], i++;
            }
            sort(b.s, b.s+b.cnt);
            
            auto &t=block[belong[r]];
            while(belong[r]==belong[j])
            {
                int id=getId(t, a[j]);
                a[j]+=x, t.s[id]=a[j], j--;
            }
            sort(t.s, t.s+t.cnt);
        
            for(int k=belong[i];k<=belong[j];k++)   
                block[k].add+=x;
        }
    }
}
using namespace Chunked;

signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
        
    init();
    while(q--)
    {
        char op[9];
        int l, r, x;
        scanf("%s%d%d%d", op, &l, &r, &x);
        
        if(*op=='M') modify(l, r, x);
        else printf("%d\n", query(l, r, x));
    }
}