求助！

__Refine__ @ 2024-11-01 19:39:28

#include<bits/stdc++.h>

using namespace std;

struct kuai
{
    int l,r,add;
}k[1000001];
int n,q,a[1000001],pos[1000001];
inline void pre()
{
    int b=sqrt(n);
    int t=n/b;
    if(n%b) t++;
    for(int i=1;i<=t;i++)
    {
        k[i].l=(i-1)*b+1;
        k[i].r=i*b;
        sort(a+1+k[i].l,a+1+k[i].r);
    }
    k[n].r=n;
    for(int i=1;i<=n;i++) pos[i]=(i-1)/b+1;
}
inline void add(int x,int y,int z)
{
    for(int i=pos[x]+1;i<=pos[y]-1;i++)
    {
        k[i].add+=z;
    }
    if(pos[x]!=pos[y])
    {
        for(int i=x;i<=k[pos[x]].r;i++) a[i]+=z;
        sort(a+1+k[pos[x]].l,a+1+k[pos[x]].r);
        for(int i=k[pos[y]].l;i<=y;i++) a[i]+=z; 
        sort(a+1+k[pos[y]].l,a+1+k[pos[y]].r);
    }

}
inline void query(int x,int y,int z)
{
    int all=0;
    for(int i=pos[x]+1;i<=pos[y]-1;i++)
    {
        int j=z-k[i].add;
        all+=k[i].r-(lower_bound(a+1+k[i].l,a+1+k[i].r,j)-a)+1;
    }
    if(pos[x]!=pos[y])
    {
        for(int i=x;i<=k[pos[x]].r;i++)
        {
            if(a[i]+k[pos[x]].add<z)all++;
        }
        for(int i=k[pos[y]].l;i<=y;i++)
        {
            if(a[i]+k[pos[y]].add<z)all++;
        }
    }

    cout<<all<<endl;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    pre();
    for(int i=1;i<=q;i++)
    {
        char o;
        cin>>o;
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if(o=='M') add(x,y,z);
        else query(x,y,z);
    }
    return 0;
}
```cpp

by swiftfox @ 2024-11-18 09:24:02

最近有点忙，只有90pts...

#include<bits/stdc++.h>
using namespace std;

struct kuai
{
    int l, r;
    long long add;
} k[3201]; 

const int MAXN = 1000001;
int n, q, a[MAXN], pos[MAXN];
int b, t; // 块大小和总块数

inline void pre()
{
    b = sqrt(n);
    t = n / b;
    if(n % b) t++;
    for(int i = 1; i <= t; i++)
    {
        k[i].l = (i-1)*b + 1;
        k[i].r = min(i*b, n);
        // 初始化懒标记
        k[i].add = 0;
        // 对每个块进行排序
        sort(a + k[i].l, a + k[i].r + 1);
    }
    for(int i = 1; i <= n; i++) pos[i] = (i-1)/b + 1;
}

inline void add_range(int x, int y, int z)
{
    int start_block = pos[x];
    int end_block = pos[y];
    if(start_block == end_block)
    {
        for(int i = x; i <= y; i++) a[i] += z;
        sort(a + k[start_block].l, a + k[start_block].r + 1);
    }
    else
    {
        // 更新起始块的部分
        for(int i = x; i <= k[start_block].r; i++) a[i] += z;
        sort(a + k[start_block].l, a + k[start_block].r + 1);
        // 更新完全覆盖的块
        for(int i = start_block + 1; i <= end_block - 1; i++) k[i].add += z;
        // 更新结束块的部分
        for(int i = k[end_block].l; i <= y; i++) a[i] += z;
        sort(a + k[end_block].l, a + k[end_block].r + 1);
    }
}

inline int query_range(int x, int y, int z)
{
    int start_block = pos[x];
    int end_block = pos[y];
    int count = 0;
    if(start_block == end_block)
    {
        for(int i = x; i <= y; i++)
        {
            if((long long)a[i] + k[start_block].add >= z) count++;
        }
    }
    else
    {
        // 查询起始块的部分
        for(int i = x; i <= k[start_block].r; i++)
        {
            if((long long)a[i] + k[start_block].add >= z) count++;
        }
        // 查询完全覆盖的块
        for(int i = start_block + 1; i <= end_block - 1; i++)
        {
            if(z - (int)k[i].add <= 0)
            {
                count += (k[i].r - k[i].l + 1);
            }
            else
            {
                // 使用 lower_bound 在排序数组中查找第一个 >= (z - add)
                int target = z - (int)k[i].add;
                int lb = lower_bound(a + k[i].l, a + k[i].r + 1, target) - a;
                count += (k[i].r - lb + 1);
            }
        }
        // 查询结束块的部分
        for(int i = k[end_block].l; i <= y; i++)
        {
            if((long long)a[i] + k[end_block].add >= z) count++;
        }
    }
    return count;
}

int main()
{

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    pre();
    for(int i = 1; i <= q; i++)
    {
        char o;
        cin >> o;
        int x, y, z;
        cin >> x >> y >> z;
        if(o == 'M') add_range(x, y, z);
        else if(o == 'A') cout << query_range(x, y, z) << "\n";
    }
    return 0;
}