SP18185 GIVEAWAY - Give Away 题解

黑影洞人 · 2022-09-12 18:35:38 · 题解

题意：

求区间大于等于 k 的值，单点赋值。

不会主席树，我们考虑分块。

• 1.准备工作

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 514514
using namespace std;
int n,m,a[N],d[N];
//d是块内排序的数组。
int block,pos[N],left[3000],right[3000],tot;
//从左到右分别是，块长，每个位置在哪个块，块左端，块右端，总共有多少个块。

• 2.预处理(分块)

都是些分块的基操，后面块内排序要注意一下。

void build(){
    block=sqrt(n);
    tot=n/block;
    if(n%block)tot++;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pos[i]=(i-1)/block+1;
        d[i]=a[i];
    }
    for(int i=1;i<=tot;i++){
        left[i]=(i-1)*block+1;
        right[i]=i*block;
    }
    right[tot]=n;
    for(int i=1;i<=tot;i++)sort(d+left[i],d+right[i]+1);
        //块内排序
}

• 3.查询操作

int query(int l,int r,int k){
    int res=0;
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++)res+=(a[i]>k);
            //局部朴素
    }else{
        for(int i=l;i<=right[pos[l]];i++)res+=(a[i]>k);
            //散块暴力跑一遍
        for(int i=left[pos[r]];i<=r;i++)res+=(a[i]>k);
        for(int i=pos[l]+1;i<=pos[r]-1;i++){
                //整块内二分，找到块内比k大的数
            if(d[right[i]]<=k)continue;
            int ps=ulower_bound(d+left[i],d+right[i]+1,k)-d;
            res+=right[i]-ps+1;
        }
    } 
    return res;
}

完整代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 54514
using namespace std;
int n,m,a[N],d[N];
int block,pos[N],left[3000],right[3000],tot;
void build(){
    block=sqrt(n);
    tot=n/block;
    if(n%block)tot++;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        pos[i]=(i-1)/block+1;
        d[i]=a[i];
    }
    for(int i=1;i<=tot;i++){
        left[i]=(i-1)*block+1;
        right[i]=i*block;
    }
    right[tot]=n;
    for(int i=1;i<=tot;i++)sort(d+left[i],d+right[i]+1);
}
int query(int l,int r,int k){
    int res=0;
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++)res+=(a[i]>k);
    }else{
        for(int i=l;i<=right[pos[l]];i++)res+=(a[i]>k);
        for(int i=left[pos[r]];i<=r;i++)res+=(a[i]>k);
        for(int i=pos[l]+1;i<=pos[r]-1;i++){
            if(d[right[i]]<=k)continue;
            int ps=lower_bound(d+left[i],d+right[i]+1,k)-d;
            res+=right[i]-ps+1;
        }
    } 
    return res;
}
signed main(){
    scanf("%d",&n);
    build();
    scanf("%d",&m); 
    int la=0;
    while(m--){
        int l,r,v;
        scanf("%d%d%d",&l,&r,&v);
        else printf("%d\n",query(l,r,v));
    }
    return 0;
}

管理员同志审核题解辛苦了。