当前位置：首页 > ds >正文

loj数列分块入门2-3

ds 2025/8/24 19:44:23

loj数列分块入门2-3

（底下有视频讲解bilibili，会自动播放）

本文和数列分块入门1 不同之处在于多了查找区间内小于某个数的最大值或者个数，区间加法的优化需要add数组来存储每段都加上的数字（类似于lzay标记）

上一期blog：loj6277数列分块入门1

先给出视频讲解，两题非常相似，一起讲了

数列分块入门2-3

6278. 数列分块入门 2

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int n,a[N],b[N],k,len,L[N],R[N],F[N],add[N];void Build()
{for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];len=sqrt(n),k=(n+len-1)/len;for(int i=1;i<=k;i++){L[i]=(i-1)*len+1;R[i]=min(i*len,n);sort(b+L[i],b+R[i]+1);F[L[i]]=i;}for(int i=1;i<=n;i++)if(F[i]==0 && i<=R[k])F[i]=(i-1)/len+1;
}
void Add(int l,int r,int c)
{int st=F[l],ed=F[r];if(st==ed){for(int i=l;i<=r;i++) a[i]+=c;for(int i=L[st];i<=R[st];i++) b[i]=a[i];sort(b+L[st],b+R[st]+1);}else{for(int i=l;i<=R[st];i++) a[i]+=c;for(int i=L[st];i<=R[st];i++) b[i]=a[i];sort(b+L[st],b+R[st]+1);for(int i=st+1;i<ed;i++) add[i]+=c;for(int i=L[ed];i<=r;i++) a[i]+=c;for(int i=L[ed];i<=R[ed];i++) b[i]=a[i];sort(b+L[ed],b+R[ed]+1);}
}int Ask(int l,int r,int c)
{int st=F[l],ed=F[r];int ans=0;if(st==ed){for(int i=l;i<=r;i++) ans+=(c > (a[i] + add[st]));}else{for(int i=l;i<=R[st];i++) ans+=(c > (a[i] + add[st]));for(int i=st+1;i<ed;i++)ans+=lower_bound(b+L[i],b+R[i]+1,c-add[i])-b-L[i];for(int i=L[ed];i<=r;i++) ans+=(c > (a[i] + add[ed]));}return ans;
}int main()
{scanf("%d",&n);Build();for(int i=1,opt,l,r,c;i<=n;i++){scanf("%d %d %d %d",&opt,&l,&r,&c);if(!opt) Add(l,r,c);else printf("%d\n",Ask(l,r,c*c));}return 0;
}

6279. 数列分块入门 3

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n,a[N],b[N],k,len,L[N],R[N],F[N],add[N];
void Build()
{for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];len=sqrt(n),k=(n+len-1)/len;for(int i = 1; i <= k; i++){L[i]=(i-1)*len+1;R[i]=min(i*len,n);sort(b+L[i],b+R[i]+1);}for(int i=1;i<=n;i++)F[i]=(i-1)/len+1;
}
void Add(int l,int r,int c)
{if(F[l]==F[r]){for(int i=l;i<=r;i++) a[i]+=c;for(int i=L[F[l]];i<=R[F[l]];i++) b[i]=a[i];sort(b+L[F[l]],b+R[F[l]]+1);return;}int st=F[l],ed=F[r];for(int i=l;i<=R[st];i++) a[i]+=c;for(int i=L[st];i<=R[st];i++) b[i]=a[i];sort(b+L[st],b+R[st]+1);for(int i=st+1;i<ed;i++) add[i]+=c;for(int i=L[ed];i<=r;i++) a[i]+=c;for(int i=L[ed];i<=R[ed];i++) b[i]=a[i];sort(b+L[ed],b+R[ed]+1);
}
int Ask(int l,int r,int c)
{int ans=-1;int st=F[l],ed=F[r];if(st==ed){for(int i=l;i<=r;i++){int val=a[i]+add[st];if(val<c) ans=max(ans,val);}return ans;}for(int i=l;i<=R[st];i++){int val=a[i]+add[st];if(val<c) ans=max(ans,val);}for(int i=st+1;i<ed;i++) {int x=c-add[i];int pos=lower_bound(b+L[i],b+R[i]+1,x)-b-1;if(pos>=L[i]-1){int val=b[pos]+add[i];if(val<c) ans=max(ans,val);}}for(int i=L[ed];i<=r;i++){int val=a[i]+add[ed];if(val<c) ans=max(ans,val);}return ans;
}int main()
{scanf("%d",&n);Build();for(int i=1,opt,l,r,c;i<=n;i++){scanf("%d %d %d %d",&opt,&l,&r,&c);if(!opt) Add(l,r,c);else printf("%d\n",Ask(l,r,c));}return 0;
}