qwq

· · 题解

这是一道很好的分块练手题。

这题的主要操作就是查询操作，修改操作肯定都会对吧。

那么如何求出所有 a_i\le k 的个数呢？

我们再看一下数据范围：n\le 10^{5},m\le 5 \times 10^{4}。

线段树？ 分块？显然分块比较好想，毕竟暴力数据结构。

不会分块的同学看看这个。

总而言之，分块的思想就是：对所有元素分成许多个块，每次操作时分开处理，对在同一个块内或者是块的一部分的元素直接暴力修改，对每个整的块再进行处理。

块的大小和个数一半由题目的数据范围决定，一般来说取 \sqrt n （这题也是）即可。但有的题目并不是分成 \sqrt n 块最好 这要视具体的题目而定。

好了，既然确定了分块，那么怎么做呢？

于是我们想到，对每个块内的所有元素进行排序，查找的时候直接二分查找即可。

修改操作太水了就不说了。

接下来就是预处理。先预处理每个块的所有信息：左端点，右端点，并把块内所有元素排序。

改的时候每次改完要重新排序。

求答案的时候如果区间在一个块内暴力扫一遍直接查 否则分成三段进行处理：两端的散块暴力查询，中间的整块，对每个块进行二分。

时间复杂度？大概是 n\times \sqrt{n} \times \log_{2}{\sqrt n} 极限数据约为 1.2s 还是有点卡的 所以时限很奇怪？

上代码：

#include <bits/stdc++.h>
using namespace std;
int L[500005],R[500005],pos[500005],b[500005],a[500005],kuai;//L,R是每个块的左端点和右端点 pos是每个点所在的块，a是初始数组，b是每个块排好序后的数组 
int getsum(int l,int r,int k){
    int x=pos[l],y=pos[r];
    if (x==y){
        int ans=0;
        for (register int i=l;i<=r;i++){
            if (a[i]<=k) ans++;
        }
        return ans;//在一个块暴力找 
    }
    int ans=0;
    for (register int i=l;i<=R[x];i++){
        if (a[i]<=k) ans++;
    }//和下面一样散块暴力找 
    for (register int i=x+1;i<=y-1;i++){
        int xs=L[i],mcqh=R[i],sum=0;
        while(xs<=mcqh){
            int mid=(xs+mcqh)/2;
            if (b[mid]>k) mcqh=mid-1;
            else xs=mid+1;
        }
        ans+=xs-L[i]; 
    }//二分找出第一个小于k的位置 
    for (register int i=L[y];i<=r;i++){
        if (a[i]<=k) ans++;
    }
    return ans;
}
int main(){
    int n,q;
    cin >> n >> q;
    for (register int i=1;i<=n;i++) cin >> a[i],b[i]=a[i];
    kuai=sqrt(n*1.0);
    for (register int i=1;i<=kuai;i++){
        L[i]=(i-1)*kuai+1,R[i]=i*kuai;
    }//预处理每个块的端点 
    if (R[kuai]!=n){
        L[kuai+1]=R[kuai]+1,R[kuai+1]=n,kuai++;
    }//分块必备，如果不能分成整块，就再加一个块 
    for (register int i=1;i<=kuai;i++){
        for (register int j=L[i];j<=R[i];j++){
            pos[j]=i;
            sort(b+L[i],b+R[i]+1); //预处理出每个点所在的块，并对b=每个块里的元素排序 
        } 
    }
    while(q--){
        char op[5];
        cin >> op;
        if (op[0]=='M'){
            int p,x;
            cin >> p >> x;
            a[p]=x;
            int bel=pos[p];
            for (register int i=L[bel];i<=R[bel];i++){
                b[i]=a[i];
            }
            sort(b+L[bel],b+R[bel]+1);//每次改了以后要重新排序 
        }
        else {
            int l,r,k;
            cin >> l >> r >> k;
            cout << getsum(l,r,k) << endl;
        }
    }
}

强化版是洛谷的教主的魔法，这题还需要打标记，处理相对来说麻烦一下大家可以去尝试一下 qwq