P13977 数列分块入门 2 题解

· · 题解

题面解释：

分块维护区间加，区间查询排名。

思路分析：

思路与教主的魔法完全相同。

散块直接暴力。修改时直接加，查询时也是直接枚举。

对于整块暴力排序，二分查询。每次被当做散块修改后都进行排序，保证其单调性。查询的时候由于保证单调性直接二分查找即可。

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,p,q,a[N],b[N],c[N];
bool cmp(int x,int y){
    return x>y;
}
void resort(int id){
    int l=id*q,r=min(l+q-1,n-1);
    for(int i=l;i<=r;i++)c[i]=a[i];
    sort(c+l,c+r+1,cmp);
}
int query(int id,int v){
    int l=id*q,r=min(l+q-1,n-1);
    v-=b[id];
    if(c[l]<v)return 0;
    int b=l,e=r;
    while(b+1<e){
        int mid=b+e>>1;
        if(c[mid]>=v)b=mid;
        else e=mid;
    }
    if(c[e]>=v)return e-l+1;
    else if(c[b]>=v)return b-l+1;
    else return 0;
}
signed main(){
    scanf("%lld",&n);
    q=(int)sqrt(n/log(n));
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]),c[i]=a[i];
    for(int l=0,r;l<n;l+=q){
        r=min(l+q-1,n-1);
        sort(c+l,c+r+1,cmp);
    }
    for(int T=1;T<=n;T++){
        int op,l,r,m;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&m);
        l--;r--;
        if(op==0){
            int _l=l,_r=r;
            for(;l%q&&l<=r;l++)a[l]+=m;
            for(;l+q-1<=r;l+=q)b[l/q]+=m;
            for(;l<=r;l++)a[l]+=m;
            resort(_l/q);
            if(_l/q!=_r/q)resort(_r/q);
        }
        else{
            int ans=0;
            for(;l%q&&l<=r;l++)if(a[l]+b[l/q]<m*m)ans++;
            for(;l+q-1<=r;l+=q)ans+=q-query(l/q,m*m);
            for(;l<=r;l++)if(a[l]+b[l/q]<m*m)ans++;
            printf("%lld\n",ans);
        }
    }
    return 0;
}