锐客网

  1. 首页 > it技术 > >

分块（区间）模板

分块

思想：将一个长度为n的数列分成m块，然后通过对这m块进行操作。属于一种暴力算法。
时间复杂度为：度是O(√n)。
分块（区间）模板
文章图片

这张图就是大致的模板了。虽然属于暴力算法，但下面这道题用分块做感觉时间差不多。
I Hate It Time Limit: 9000/3000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 108077Accepted Submission(s): 40504

Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0 学生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
给你们链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
这道题可以用线段树和分块做。线段树的可以看这一篇A - I Hate It HDU - 1754 单点更新 区间查询

#include #include #include using namespace std; int node[200001],belong[200001]; //node是点，belong是某点属于哪个“block”内 int maxn[20001]; //“block”块中最大的值 int n,m; int block,num,l[20001],r[20001]; //block表示块的大小，num表示块的数量 //l表示第i个块的左边界，r表示第i个块的右边界 void build() { block=sqrt(n); num=n/block; if(n%block) num++; for(int i=1; i<=n; i++) { cin>>node[i]; belong[i]=(i-1)/block+1; } for(int i=1; i<=num; i++) { l[i]=block*(i-1)+1; r[i]=block*i; } r[num]=n; for(int i=1; i<=num; i++) { for(int j=l[i]; j<=r[i]; j++) maxn[i]=max(maxn[i],node[j]); } } void updata(int a,int b) { node[a]=b; maxn[belong[a]]=max(maxn[belong[a]],b); } int query(int a,int b) { int ans=0; for(int i=a; i<=min(r[belong[a]],b); i++) { ans=max(ans,node[i]); } for(int i=belong[a]+1; i>n>>m) { memset(maxn,0,sizeof(maxn)); build(); char c; int a,b; while(m--) { cin>>c>>a>>b; if(c=='Q') { cout<


时间比较
分块（区间）模板
文章图片

后面两个在这A - I Hate It HDU - 1754 单点更新 区间查询；



    推荐阅读


    上一篇：最长公共子序列

    下一篇：Mybatis练习(1)