博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
高级的暴力(一)——分块
阅读量:6643 次
发布时间:2019-06-25

本文共 1407 字,大约阅读时间需要 4 分钟。

在某大佬的帮助下我今天get到了分块

简单来说分块就是可以把块分成某些奇怪的大小,使之达到优秀的复杂度。but我现在只会把块分成根号大小,然后我们修改一个点的

信息时就可以顺便修改次点所在块的信息(O(1))。接着当我们查询[L,R]这段区间,的时候,对于中间的大块可以直接拿来用,对于两

边不完整的块则直接暴力查询(都是根号n,)。

差不多就这样,最后附上用分块过的代码

 

[cpp] 
 
 
  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstring>  
  4. #include<algorithm>  
  5. #include<cmath>  
  6. using namespace std;  
  7. const int maxn=1e5+7;  
  8. int num,block,l[maxn],r[maxn],n,m,p,x,t,belong[maxn];  
  9. long long Max[maxn],a[maxn];  
  10. void build()  
  11. {  
  12.     block=sqrt(n);//块的太小   
  13.     num=n/block;  
  14.     if(n%block) num++;//块的个数,记得特判   
  15.     for(int i=1;i<=num;i++)  
  16.     {  
  17.         l[i]=(i-1)*block+1;  
  18.         r[i]=i*block;  
  19.     }//确定每个块的左右区间   
  20.       
  21.     r[num]=n;//不要忘记最右为n   
  22.     for(int i=1;i<=n;i++)    belong[i]=(i-1)/block+1;//确定每个 点所属的块   
  23.     for(int i=1;i<=num;i++)  
  24.        for(int j=l[i];j<=r[i];j++)  
  25.        Max[i]=max(Max[i],a[j]);//预处理   
  26. }  
  27. void update(int x,int date)//单点更改   
  28. {  
  29.     a[x]+=date;  
  30.     Max[belong[x]]=max(Max[belong[x]],a[x]);  
  31. }  
  32. long long ask(int x,int y)//区间查询   
  33. {  
  34.     long long ans=0;  
  35.     if(belong[x]==belong[y])  
  36.     {  
  37.         for(int i=x;i<=y;i++)  
  38.         {  
  39.             ans=max(ans,a[i]);  
  40.         }  
  41.         return ans;  
  42.     }//如果左右端点在同一块内则直接暴力查询   
  43.     for(int i=x;i<=r[belong[x]];i++)  
  44.     ans=max(ans,a[i]);  
  45.     for(int i=belong[x]+1;i<belong[y];i++)  
  46.     ans=max(ans,Max[i]);//如果左右端点需跨块,那么对于中间大块的信息直接使用  
  47.     for(int i=l[belong[y]];i<=y;i++)  
  48.     ans=max(ans,a[i]);// 两端不完整的的块暴力查询   
  49.     return ans;  
  50. }  
  51. int main()  
  52. {  
  53.     scanf("%d",&n);  
  54.     build();  
  55.     scanf("%d",&m);  
  56.     while(m--)  
  57.     {  
  58.         scanf("%d%d%d",&t,&p,&x);  
  59.         if(t==1) update(p,x);  
  60.         else printf("%lld\n",ask(p,x));  
  61.     }  
  62.     return 0;  
  63. }   

转载于:https://www.cnblogs.com/LQ-double/p/5971332.html

你可能感兴趣的文章
java中文件操作《一》
查看>>
怎么预防sql注入攻击
查看>>
HTTPS原理
查看>>
gispro试用版账户注册
查看>>
转:测试计划(出处:: 51Testing软件测试网--zfx081)
查看>>
#、#@、## in C++宏定义
查看>>
VM虚拟机下的Linux不能上网
查看>>
后缀数组小结
查看>>
myEclipse 输入时英文自动变成2个字符大小
查看>>
gulp自动化打包及静态文件自动添加版本号
查看>>
对ASP.NET程序员非常有用的85个工具
查看>>
iOS小技巧总结
查看>>
2016-8-25
查看>>
2016-9-22
查看>>
浅谈数据库系统中的cache(转)
查看>>
Ext.form.field.Hidden隐藏字段
查看>>
openNebula dubug
查看>>
Codeforces Round #413(Div. 1 + Div. 2, combined)——ABCD
查看>>
js获取select标签选中的值
查看>>
OpenGL Type
查看>>