首页 > 其他分享 >分块--解决区间问题

分块--解决区间问题

时间:2024-04-15 10:58:19浏览次数:20  
标签:10 2e9 分块 -- len int long 区间

什么时候用分块?

当你发现正常数据结构无法解决的时候(比如维度特别多,很不方便或者炸空间),或者复杂到要3个 $log$ 以上才能解决时。(主要还是得看数据范围,分块的做法一般都是 $O(\sqrt{n})$ 及以上的

如何分块?

定一个块长 $B$ ,整个序列就会被分成 $\floor{n/B}$ 块,对于末尾的不完整的块,可以直接暴力修改查询

对于一个区间,会分解成两个不完整的块和中间的一些完整的块,那么我们就可以暴力不完整的块,对于完整的块我们只需要打个标记就可以了

 

例题:
P2801 教主的魔法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int a[N],e[N],be[N];
int L[N],R[N],tag[N];
void make(int x){ //对块进行操作,每个块都排序,那么我们在查询的时候就可以直接二分出最接近c的数,然后O(1)求出答案
    for(int i=L[x];i<=R[x];i++) e[i]=a[i]; //由于a还在修改的时候有用,所以我们要另开一个数组
    sort(e+L[x],e+R[x]+1);
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,q; cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    int len=sqrt(n),tot=(n+len-1)/len; //定义块长,分块
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*len+1,R[i]=min(n,i*len); //求出每个块的左端点和右端点
        for(int j=L[i];j<=R[i];j++) be[j]=i; //be是belong,序列中的下标映射到块的下标
        make(i);
    }
    while(q--){
        char check; cin>>check;
        if(check=='M'){
            int l,r,w; cin>>l>>r>>w;
            if(be[l]==be[r]){ //如果在同一个块,直接暴力
                for(int i=l;i<=r;i++) a[i]+=w;
                make(be[l]); //修改完之后要更新
            }
            else{
                for(int i=l;i<=R[be[l]];i++) a[i]+=w; //两个不完整的块,暴力
                for(int i=L[be[r]];i<=r;i++) a[i]+=w;
                make(be[l]),make(be[r]);
                for(int i=be[l]+1;i<=be[r]-1;i++) tag[i]+=w;//完整的块,标记
            }
        }
        else{ 
            int cnt=0,l,r,c; cin>>l>>r>>c;
            if(be[l]==be[r])
                for(int i=l;i<=r;i++) cnt+=(a[i]+tag[be[i]]>=c);
            else{
                for(int i=l;i<=R[be[l]];i++) cnt+=(a[i]+tag[be[i]]>=c);
                for(int i=L[be[r]];i<=r;i++) cnt+=(a[i]+tag[be[i]]>=c);
                for(int i=be[l]+1;i<=be[r]-1;i++)
                    cnt+=e+1+R[i]-lower_bound(e+L[i],e+R[i]+1,c-tag[i]);
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}

Farmer John's Favorite Function - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

由于从 $k$ 这个位置开始,向后推的话,会发现,当我们推到 $k+6$ 的时候基本上 $a_k$ 的修改的贡献就小于 $1$ 了,也就是说,对于每个修改的 $a_k$,他的影响范围最多到 $k+6$,可以把值设为 2e9 自己推一下就可以推出来,所以我们的块长至少是 $6$,但是考虑保险设为 $10$ 也一定不错,此时对于每一次查询,我们直接修改 $a_k$ 所在的块,并且记录贡献,由于贡献是递减的,有可能在区间中的某个点之前他的贡献是 $e_k+1$,所以我们要倒着推,我们设这个区分点为 $f_i$,从前向后推,如果说存在 $f_j >= 2e9$ 那么就无解,因为我们的数最大不超过 2e9,对于最后一块区间,我们直接暴力修改即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7,inf=2e9;
int n,q,tot;
int a[N],be[N],L[N],R[N],f[N],e[N];
int sqrtt(int x){
    int x_=sqrtl(x);
    while(x_*x_>x) x_--;
    while((x_+1)*(x_+1)<=x) x_++;
    return x_;
}
void make(int x){ //开方,由于考虑浮点数影响,可以求稳更新一下sqrt(x)
    if(x==tot) return;
    e[x]=0; 
    for(int i=L[x];i<=R[x];i++) e[x]=sqrtt(a[i]+e[x]);
    f[x]=e[x]+1;
    for(int i=R[x];i>=L[x]&&f[x]!=inf;i--) f[x]=min(inf,f[x]*f[x]-a[i]);
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    int len=max((int)10,(int)sqrt(n));
    tot=(n+len-1)/len;
    for(int i=1;i<=tot;i++){
        L[i]=(i-1)*len+1,R[i]=min(n,i*len);
        for(int j=L[i];j<=R[i];j++) be[j]=i;
        make(i);    
    }
    while(q--){
        int k,x; cin>>k>>x;
        a[k]=x,make(be[k]);
        int res=0;
        for(int i=1;i<=tot-1;i++) res=e[i]+(res>=f[i]);
        for(int i=L[tot];i<=n;i++) res=sqrtt(res+a[i]);
        cout<<res<<endl;
    }
    return 0;
}

 

标签:10,2e9,分块,--,len,int,long,区间
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18135420

相关文章

  • 从零手写实现 apache Tomcat-01-入门介绍
    自己如何实现?要实现一个简单版本的Tomcat,整体思路如下了解Tomcat的基本原理:Tomcat是一个开源的JavaServlet容器和Web服务器,它能够运行JavaServlet和JavaServerPages。Tomcat是基于Java的,它是用Java编写的。创建一个简单的HTTP服务器:创建一个Jav......
  • 十大管理每个过程定义以及作用
    一、整体管理1、制定项目章程制定一份正式批准并授权项目经理在项目活动中使用活动资源的文件。明确了项目于组织战略目标之间的直接联系;确立了项目的正式地位;展示了组织对项目的承诺。2、制定项目管理计划组织、准备和协调项目计划的其他组成部分的文件,并把它们整合成一份综合的......
  • 小程序对输入框输入值进行限制(输入框完全控制无法实现)
    1.需求例如数值输入只能输入两位小数2.问题1)如果采用输入之后去通过正则之类的去替换掉输入的值然后再赋值给input,会出现一个变化过程,也就是说只要操作input值就存在该问题,并且光标会移动到最后,小程序原生可以控制光标位置(但是小程序方法返回字符串和直接设置值一样有一......
  • 项目整合管理
             ......
  • BackTrader 中文文档(二)
    原文:www.backtrader.com/概念平台概念原文:www.backtrader.com/docu/concepts/这是平台某些概念的集合。它试图收集可在使用平台时有用的信息片段。开始之前所有小代码示例都假设以下导入可用:importbacktraderasbtimportbacktrader.indicatorsasbtindimportbac......
  • 上周热点回顾(4.8-4.14)
    热点随笔:· 园子周边第3季—设计初稿预览:2024夏天穿上博客园T恤showyourcode (博客园团队)· 园子开店记:被智能的淘宝处罚,说是“预防性的违规” (博客园团队)· 拥抱开源更省钱「GitHub热点速览」 (削微寒)· C#使用PaddleOCR进行图片文字识别✨ (mingupupup)· .NE......
  • centos7 安装supervisor教程以及常见问题
    目录简介Supervisor是一个进程控制系统。它是一个C/S系统(注意:其提供WEB接口给用户查询和控制)。它允许用户去监控和控制在类UNIX系统的进程。它的目标与launchd、daemontools和runit有些相似。但是与它们不一样的是、它不是作为init(进程号pid是1)运行。它是......
  • BackTrader 中文文档(四)
    原文:www.backtrader.com/数据供稿-过滤器过滤器原文:www.backtrader.com/docu/filters/此功能是相对较晚添加到backtrader中的,并且必须适应已经存在的内部结构。这使得它不像希望的那样灵活和100%功能齐全,但在许多情况下仍然可以实现目的。尽管实现尝试允许即插即用的......
  • Centos7 中使用Supervisor守护进程
    配置supervisor实现进程守护1.安装supervisoryuminstallSupervisor 2.启动服务supervisord-c/etc/supervisord.conf 进入cd/etc目录找到supervisord.conf配置文件和supervisord.d文件夹,使用vim编辑supervisord.conf文件,拉到最底部我们可以看到 fil......
  • 函数式编程思想 VS 可变性理论 20240415
    函数式编程(FunctionalProgramming,FP)是一种编程范式,它将计算视为数学函数的求值,并避免使用程序状态以及易变对象。函数式编程的核心思想包括:不可变性(Immutability):在函数式编程中,数据是不变的。一旦创建了一个数据结构,就不能再改变它。所有的操作都会产生新的数据结构。纯......