qaq

· · 题解

分块板子？多倍经验！

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

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

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

线段树？ 分块？显然分块比较好想，毕竟暴力数据结构。 而且，分块码量很小，是万能数据结构。

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

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

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

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

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

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

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

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

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

时间复杂度？大概是 O(n\times \sqrt{n} \times \log_{2}{\sqrt n})。

上代码：

#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,sum=R[i]-mid+1;
            else xs=mid+1;
        }
        ans+=sum;//二分找出第一个>=k的数 后面的都可以
    }
    for (register int i=L[y];i<=r;i++){
        if (a[i]>=k) ans++;
    }
    return ans;
}
int main(){
    int n,q;
    cin >> n;
    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=每个块里的元素排序 
        } 
    }
    cin >> q; 
    while(q--){
        char op[5];
        cin >> op;
        if (op[0]=='1'){
            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。

同类型的题还有SP3261，UVA12003，就当四倍经验吧(。