分块 && 例题 I Hate It HDU - 1754
分块算法:
分块就是对暴力方法的一种优化: _
假设我们总共的序列长度为n,然后我们把它切成√n 块,然后把每一块里的东西当成一个整体来看,
完整块:被操作区间完全覆盖的块
不完整块:操作区间不完全覆盖的块
在对区间的询问中,对于完整块我们就去找维护这个块的数组。比如我们要找[l,r]这个区间中所有数的和,那么我们再把这n个数分块之后肯定要找一个数组去记录一下每一块中所有数的和(如果按照暴力的方式肯定是从l到r遍历,而分块对暴力方法的优化就是在完整块上不需要去遍历)。
对于不完整块的询问,那就遍历这个不完整块就可以了
其实和线段树很相似,分块的实际代码比线段树要简单些!
复杂度:O( nsqrt( n ) ) + O( nsqrt( m ) ) (n是序列长度,m是查询区间次数)
题目:
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数,代表这N个学生的初始成绩,其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ,和两个正整数A,B。
当C为'Q'的时候,表示这是一条询问操作,它询问ID从A到B(包括A,B)的学生当中,成绩最高的是多少。
当C为'U'的时候,表示这是一条更新操作,要求把ID为A的学生的成绩更改为B。
Output对于每一次询问操作,在一行里面输出最高成绩。Sample Input
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin
分析:
题意很清晰,按照对分块的理解我们就应该找一个数组去维护一下分块后每一块的区间最大值。
具体分块看代码:
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<math.h>
6 using namespace std;
7 const int maxn=200005;
8 int n,m,a[maxn],block,num,l[maxn],r[maxn],maxx[maxn],belong[maxn];
9 //l数组决定分块后每一块区间的左端点,r数组决定分块后每一块区间的右端点
10 //belong数组决定这一个位置属于哪一个块
11 //maxx数组就是维护分块后区间最大值的
12 //num代表一共有多少块
13 void build()
14 {
15 block=sqrt(n);
16 num=n/block;
17 for(int i=1; i<=num; ++i)
18 {
19 l[i]=block*(i-1)+1;
20 r[i]=block*i;
21 }
22 r[num]=n;
23
24 for(int i=1; i<=num; ++i)
25 {
26 int ans=0;
27 for(int j=l[i]; j<=r[i]; ++j)
28 {
29 ans=max(ans,a[j]);
30 belong[j]=i;
31 }
32 maxx[i]=ans;
33 }
34 }
35 int query(int x,int y)
36 {
37 int ans=0;
38 if(belong[x]==belong[y])
39 {
40 for(int i=x; i<=y; ++i)
41 {
42 ans=max(ans,a[i]);
43 }
44 }
45 else
46 {
47 for(int i=x; i<=r[belong[x]]; i++) ans=max(ans,a[i]); //对于不完整块要遍历
48 for(int i=belong[x]+1; i<belong[y]; i++) //完整块直接访问维护数组maxx就完了
49 ans=max(ans,maxx[i]);
50 for(int i=l[belong[y]]; i<=y; i++) ans=max(ans,a[i]); //对于不完整块要遍历
51 }
52 return ans;
53 }
54 void update(int x,int y)
55 {
56 maxx[belong[x]]=max(maxx[belong[x]],y);
57 a[x]=y; //更新的时候维护最大值数组要更新且原位置也要更新
58 }
59 int main()
60 {
61 int x,y;
62 char ch[5];
63 while(~scanf("%d%d",&n,&m))
64 {
65 for(int i=1;i<=n;++i) scanf("%d",&a[i]);
66 build();
67 while(m--)
68 {
69 scanf("%s%d%d",ch,&x,&y);
70 if(ch[0]=='Q')
71 {
72 printf("%d\n",query(x,y));
73 }
74 else
75 {
76 update(x,y);
77 }
78 }
79 }
80 return 0;
81 }
最新文章
- 【MySQL】使用Length和Cast函数计算TEXT类型字段的长度
- Python爬虫爬取百度贴吧的帖子
- RecyclerView使用
- java.lang.RuntimeException: Fail to connect to camera service问题
- MYSQL-- binlog事件详解
- ruby 疑难点之—— attr_accessor attr_reader attr_writer
- C#double转化成字符串 保留小数位数, 不以科学计数法的形式出现
- 九度OJ 1348 数组中的逆序对 -- 归并排序
- x86与x64与x86_64
- linux下常用基本命令操作
- C#多显示器转换的两种方法——SetWindowPos,Screen
- IntelliJ Idea 经常使用快捷键列表
- MySQL分表
- django admin 支持时间更改
- svgalib_1.4.3 移植
- Python入门到精通学习书籍推荐!
- 自己写bitmap
- JS函数机制小结
- 解决连锁零售行业IT运维管理四大困境
- C# 正则表达式入门