1.分块思想:将一个数组分成若干块,每次修改或查询时候对整块一起修改,多余的暴力修改(分块是对暴力的优化)
分块初始化:
void init(){
int len=sqrt(n);
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;//每个数处于哪一段
s[i]=w[i];
}
for(int i=1;i<=ceil((double)n/len);i++){
int l=lower_bound(id+1,id+n+1,i)-id;
int r=upper_bound(id+1,id+n+1,i)-id-1;
le[i]=l;
ri[i]=r;//每段的左右边界
sort(w+l,w+r+1);
// cout<<i<<" "<<l<<" "<<r<<endl;
}
}
2.操作
1.区间修改
1)只有加法
思路:不成整块的暴力修改,整块的标记修改(感觉和线段树lazytag很像
void insert(int l,int r,int x){
int len=sqrt(n);
for(int i=l;i<=ri[l];i++){
w[i]+=x;
}
for(int i=id[l]+1;i<id[r];i++){
add[i]+=x;
}
if(id[l]==id[r]) return ;
for(int i=le[id[r]];i<=r;i++){
w[i]+=x;
}
}
只有乘法的相似
2)加乘结合
思路:每次更新时候先把不成整段的标记使用后清零再暴力更新,其他的做加法时在加法标记上更新,乘法时候加法标记和乘法标记都要更新
struct fk{//结构体封装
int w[100010],id[100010],add[350],mul[350],n,len,le[350],ri[350],mod;
void init(){
mod=1e4+7;
for(int i=1;i<=ceil((double)n/len);i++) mul[i]=1;
for(int i=1;i<=n;i++) id[i]=(i-1)/len+1;
for(int i=1;i<=n/len;i++){
le[i]=lower_bound(id+1,id+n+1,i)-id;
ri[i]=upper_bound(id+1,id+n+1,i)-id-1;
}
if(n%len){
le[n/len+1]=lower_bound(id+1,id+n+1,n/len+1)-id;
ri[n/len+1]=n;
}
}
void to_add(int l,int r,int x){
if(id[l]==id[r]){
for(int i=le[id[l]];i<=ri[id[l]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
for(int i=l;i<=r;i++){
w[i]=(w[i]+x)%mod;
}
add[id[l]]=0;
mul[id[l]]=1;
return ;
}
for(int i=le[id[l]];i<=ri[id[l]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
for(int i=le[id[r]];i<=ri[id[r]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
add[id[l]]=add[id[r]]=0;
mul[id[l]]=mul[id[r]]=1;
for(int i=l;i<=ri[id[l]];i++) w[i]=(w[i]+x)%mod;
for(int i=id[l]+1;i<id[r];i++) add[i]=(add[i]+x)%mod;
for(int i=le[id[r]];i<=r;i++) w[i]=(w[i]+x)%mod;
}
void to_mul(int l,int r,int x){
if(id[l]==id[r]){
for(int i=le[id[l]];i<=ri[id[l]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
for(int i=l;i<=r;i++){
w[i]=w[i]*x%mod;
}
add[id[l]]=0;
mul[id[l]]=1;
return ;
}
for(int i=le[id[l]];i<=ri[id[l]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
for(int i=le[id[r]];i<=ri[id[r]];i++) w[i]=(w[i]*mul[id[i]]+add[id[i]])%mod;
add[id[l]]=add[id[r]]=0;
mul[id[l]]=mul[id[r]]=1;
for(int i=l;i<=ri[id[l]];i++) w[i]=w[i]*x%mod;
for(int i=id[l]+1;i<id[r];i++){
add[i]=add[i]*x%mod;
mul[i]=mul[i]*x%mod;
}
for(int i=le[id[r]];i<=r;i++) w[i]=w[i]*x%mod;
}
int get_ans(int i){//加法标记已经在每次操作时候都乘上乘法标记了,所以先加后乘
int ans=w[i];
ans=ans*mul[id[i]]%mod;
ans=(ans+add[id[i]])%mod;
return ans;
}
};
?3)开根号
每个数在有限次开根号后向下取整都会变成0/1,分块记录一块是否都是0/1,否则暴力修改(int范围内每个数最多更新log(2)31=5次,时间复杂度正确
void do_sqrt(int l,int r){
if(id[l]==id[r]){
for(int i=l;i<=r;i++){
sum[id[l]]-=w[i];
w[i]=sqrt(w[i]);
sum[id[l]]+=w[i];
}
bool o=true;
for(int i=le[id[l]];i<=ri[id[l]];i++){
if(w[i]!=0&&w[i]!=1){
o=false;
break;
}
}
ok[id[l]]=o;
}else{
if(!ok[id[l]]){
for(int i=l;i<=ri[id[l]];i++){
sum[id[l]]-=w[i];
w[i]=sqrt(w[i]);
sum[id[l]]+=w[i];
}
bool o=true;
for(int i=le[id[l]];i<=ri[id[l]];i++){
if(w[i]>1){
o=false;
break;
}
}
ok[id[l]]=o;
}
for(int i=id[l]+1;i<id[r];i++){
// if(ok[i]) cout<<"*";
if(!ok[i]){
bool o=true;
for(int j=le[i];j<=ri[i];j++){
sum[i]-=w[j];
w[j]=sqrt(w[j]);
sum[i]+=w[j];
// cout<<j<<" "<<w[j]<<endl;
if(w[j]>1) o=false;
}
ok[i]=o;
}
}
if(!ok[id[r]]){
for(int i=le[id[r]];i<=r;i++){
sum[id[r]]-=w[i];
w[i]=sqrt(w[i]);
sum[id[r]]+=w[i];
}
bool o=true;
for(int i=le[id[r]];i<=ri[id[r]];i++){
if(w[i]!=0&&w[i]!=1){
o=false;
break;
}
}
ok[id[r]]=o;
}
}
}
2.区间查询
1)小于某数的数量
记录一个原数列和一个每块都从小到大排好序的数列,不是整段的暴力查找,是整段的二分查找
void ad(int l,int r,long long x){
if(id[l]==id[r]){
for(int i=l;i<=r;i++){
s[i]+=x;
}
for(int i=le[id[l]];i<=ri[id[l]];i++){
w[i]=s[i];
}
sort(w+le[id[l]],w+ri[id[l]]+1);
return ;
}
for(int i=l;i<=ri[id[l]];i++){
s[i]+=x;
}
for(int i=le[id[l]];i<=ri[id[l]];i++) w[i]=s[i];
sort(w+le[id[l]],w+ri[id[l]]+1);
for(int i=id[l]+1;i<id[r];i++){
add[i]+=x;
}
for(int i=le[id[r]];i<=r;i++){
s[i]+=x;
}
for(int i=le[id[r]];i<=ri[id[r]];i++) w[i]=s[i];
sort(w+le[id[r]],w+ri[id[r]]+1);
}//更新操作时候注意数的对应,应在保存原数列的数组上更新然后再转移到排序的数列
int query(int l,int r,long long x){
int ans=0;
if(id[l]==id[r]){
for(int i=l;i<=r;i++){
if(s[i]+add[id[l]]<x) ans++;
}
return ans;
}
for(int i=l;i<=ri[id[l]];i++){
if(s[i]+add[id[l]]<x) ans++;
}
for(int i=id[l]+1;i<id[r];i++){
ans=ans+lower_bound(w+le[i],w+ri[i]+1,x-add[i])-(w+le[i]);//二分查找
}
for(int i=le[id[r]];i<=r;i++){
if(s[i]+add[id[r]]<x) ans++;
}
return ans;
}
2).查询众数
众数一定来源于未构成整块的数的值和整块中出现的众数,要预处理出整块l~r的众数
struct fk{
int n,len,gs,w[40010],ans[36][36][40010],cs[36][40010],id[40010],le[36],ri[36];
int q[40010];
node qr[36][36];
void init(){
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;
if(i%len==1){
for(int j=1;j<=gs;j++){
cs[id[i]][j]=cs[id[i]-1][j];
}
}
cs[id[i]][w[i]]++;
}
for(int l=1;l<=ceil((double)n/len);l++){
for(int r=l;r<=ceil((double)n/len);r++){
for(int i=1;i<=gs;i++){
ans[l][r][i]=cs[r][i]-cs[l-1][i];
if(ans[l][r][i]>qr[l][r].gs||(ans[l][r][i]==qr[l][r].gs&&q[i]<q[qr[l][r].w])){
qr[l][r].w=i;
qr[l][r].gs=ans[l][r][i];
}
}
}
}//预处理块l~块r中出现的众数
for(int i=1;i<=n/len;i++){
le[i]=lower_bound(id+1,id+n+1,i)-id;
ri[i]=upper_bound(id+1,id+n+1,i)-id-1;
}
if(n%len){
le[n/len+1]=lower_bound(id+1,id+n+1,n/len+1)-id;
ri[n/len+1]=n;
}
}
int query(int l,int r){
int ans_gs=0,ans_w=0;
if(id[l]==id[r]){
for(int i=l;i<=r;i++){
// cout<<i<<" "<<w[i]<<endl;
ans[0][0][w[i]]++;
if(ans[0][0][w[i]]>ans_gs||(ans_gs==ans[0][0][w[i]]&&q[w[i]]<q[ans_w])){
ans_gs=ans[0][0][w[i]];
ans_w=w[i];
}
}
for(int i=l;i<=r;i++) ans[0][0][w[i]]--;
return ans_w;
}
ans_gs=qr[id[l]+1][id[r]-1].gs;
ans_w=qr[id[l]+1][id[r]-1].w;
for(int i=l;i<=ri[id[l]];i++){
ans[id[l]+1][id[r]-1][w[i]]++;
if(ans[id[l]+1][id[r]-1][w[i]]>ans_gs||(ans[id[l]+1][id[r]-1][w[i]]==ans_gs&&q[w[i]]<q[ans_w])){
ans_gs=ans[id[l]+1][id[r]-1][w[i]];
ans_w=w[i];
}
}
for(int i=le[id[r]];i<=r;i++){
ans[id[l]+1][id[r]-1][w[i]]++;
if(ans[id[l]+1][id[r]-1][w[i]]>ans_gs||(ans[id[l]+1][id[r]-1][w[i]]==ans_gs&&q[w[i]]<q[ans_w])){
ans_gs=ans[id[l]+1][id[r]-1][w[i]];
ans_w=w[i];
}
}
for(int i=l;i<=ri[id[l]];i++) ans[id[l]+1][id[r]-1][w[i]]--;
for(int i=le[id[r]];i<=r;i++) ans[id[l]+1][id[r]-1][w[i]]--;
return ans_w;
}
};
?3.插入
正常操作,对于每个过大的块分成两半
void rebuild(int id){//将这一块后所以块向后推,这一块分成两半
gs++;
int las[1010],lassz;
for(int i=1;i<=size[id+1];i++){
las[i]=w[id+1][i];
}
lassz=size[id+1];
for(int i=id+2;i<=gs;i++){
int s[1010],sz;
for(int j=1;j<=size[i];j++){
s[j]=w[i][j];
}
sz=size[i];
for(int j=1;j<=lassz;j++){
w[i][j]=las[j];
}
size[i]=lassz;
for(int j=1;j<=sz;j++){
las[j]=s[j];
}
lassz=sz;
}
int k=size[id]/2;
for(int i=k+1;i<=size[id];i++){
las[i-k]=w[id][i];
}
size[id+1]=size[id]-k;
for(int i=1;i<=size[id+1];i++) w[id+1][i]=las[i];
size[id]=k;
}
void insert(int k,int x){
int p=1;
while(k-size[p]>0){
k-=size[p];
p++;
}
for(int i=k;i<=size[p]+1;i++){
int o=w[p][i];
w[p][i]=x;
x=o;
}
size[p]++;
if(size[p]>800){//块过大,重构
rebuild(p);
}
}
?
|