【算法每日一练]-结构优化（保姆级教程 篇6 分块，倍增）#HDU4417超级马里奥 #poj2019玉米田 #POJ3368频繁值
今天知识点：
区间统计不超过h的值；
查询二维区间的极差；
求区间最频繁数；
目录
HDU4417：超级马里奥
思路：
poj2019:玉米田
思路：
POJ3368:频繁值
思路：
HDU4417：超级马里奥
在长n的道路中。每个i点都有高度Hi的砖，输入l,r,h表示他最高能跳h，问在区间[l,r]中最多可以跳多少砖块？
输入：
1
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3
输出：
Case1:
4 0 0 3 1 2 0 1 5 1
思路：
其实就是统计区间中有多少个不超过h的值。
我们采用分块处理，对于完整的块，可以采用排序，然后upper_bound直接返回个数。不完整的块暴力所查区间
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int L[maxn],R[maxn],be[maxn];
int a[maxn],tmp[maxn],n,m;
void build(){
int t=sqrt(n);
int num=n/t;
if(n%num)num++;
for(int i=1;i<=num;i++){
L[i]=(i-1)*t+1;R[i]=i*t;
}
R[num]=n;
for(int i=1;i<=n;i++){
be[i]=(i-1)/t+1;
}
for(int i=1;i<=num;i++){
sort(tmp+L[i],tmp+1+R[i]);//每块排序
}
}
int query(int l,int r,int h){
int ans=0;
if(be[l]==be[r]){//在同一块就暴力
for(int i=l;i<=r;i++)
if(a[i]<=h)ans++;
}
else{
for(int i=l;i<=R[be[l]];i++){//左端块暴力
if(a[i]<=h)ans++;
}
for(int i=be[l]+1;i<be[r];i++){//中间块直接lowerbound
ans+=upper_bound(tmp+L[i],tmp+R[i]+1,h)-tmp-L[i];//直接获取能跳过去的个数
}
for(int i=L[be[r]];i<=r;i++){//右端块暴力
if(a[i]<=h) ans++;
}
}
return ans;
}
int main(){
int t;cin>>t;
for(int cas=1;cas<=t;cas++){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
tmp[i]=a[i];
}
build();
printf("Case %d:\n",cas);
while(m--){
int l,r,h;
scanf("%d%d%d",&l,&r,&h);
printf("%d\n",query(++l,++r,h));
}
}
}
poj2019:玉米田
为了寻找平坦的地来种玉米，在n*n公顷的农场中，每公顷都有一个整数高度，查询k次，对于(x,y)为左顶点的c*c子矩阵中的最大和最小高度差是多少？
输入：
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
思路：
首先这题是个离线的区间最值题，倍增就行了
一维max不满足减法，所以不能直接建立二维max数组，那么就用多个一维的max数组等价成二维的即可。
但是我们仍然开三维数组f[x][y][j]表示(x,y)点向右扩展1<<j长度的最值
因为每次查询都要取一次log，当查询量较大时候就不行了，所以可以利用动态规划来初始化log函数因为如果i&(i-1)是0，那么log(i)=log(i-1)+1，否则log(i)=log(i-1)。
void initlog(){
b[0]=-1;
for(int i=1;i<maxn;i++){
b[i]=(i&(i-1))?b[i-1]:b[i-1]+1;
}
}#include <bits/stdc++.h>
using namespace std;
const int maxn=260;
int a[maxn][maxn],b[maxn];
int f_max[maxn][maxn][11],f_min[maxn][maxn][11];//f[x][y][j]表示(x,y)点向右扩展1<<j长度的最值
void initlog(){
b[0]=-1;
for(int i=1;i<maxn;i++){
b[i]=(i&(i-1))?b[i-1]:b[i-1]+1;
}
}
void ST(int n){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
f_max[k][i][0]=f_min[k][i][0]=a[k][i];//初始化
for(int k=1;k<=n;k++)//一行一行处理
for(int j=1;j<=b[n];j++)//j是二进制大小
for(int i=1;i+(1<<j)-1<=n;i++){//i是每个列值
f_max[k][i][j]=max(f_max[k][i][j-1],f_max[k][i+(1<<(j-1))][j-1]);//更新最大值和最小值
f_min[k][i][j]=min(f_min[k][i][j-1],f_min[k][i+(1<<(j-1))][j-1]);
}
}
void solve(int x,int y,int c){//从（x，y）开始向右下扩展c长度
int k=b[c];
int maxx=-1,minx=0x3f3f3f3f;
int l=y,r=y+c-1;
for(int i=x;i<x+c;i++){//查询每行的最值
maxx=max(maxx,max(f_max[i][l][k],f_max[i][r-(1<<k)+1][k]));
minx=min(minx,min(f_min[i][l][k],f_min[i][r-(1<<k)+1][k]));
}
printf("%d\n",maxx-minx);
}
int main(){
int n,k,c;
int x,y;
initlog();
while(scanf("%d%d%d",&n,&c,&k)!=EOF){//输入n大小，c大小，k次数
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
ST(n);
for(int i=0;i<k;i++){
scanf("%d%d",&x,&y);
solve(x,y,c);
}
}
}
POJ3368:频繁值
给定一个非递减的整数序列n，进行q次查询，确定i到j之间的最频繁的值
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
输出
1
4
3
思路：
注意到非递减的性质，不难想到对应的频繁数1 2 1 2 3 4 1 1 2 3然后就转化成了离线的区间最值。
直接设置f[i][j]表示存放[i,i+2^j-1]长度2^j的最值，初始化f[i][0]，然后在查询区间的时候注意单独处理最左边的元素，剩余的区间就能直接查询了
#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
int a[maxn],b[maxn],f[maxn][20];//a存放数据，b存放log值，f存放[i,i+2^j-1]长度2^j
void initlog(){
b[0]=-1;
for(int i=1;i<maxn;i++){
b[i]=(i&(i-1))?b[i-1]:b[i-1]+1;
}
}
void ST(int n){
for(int j=1;j<=b[n];j++){
for(int i=1;i<=n-(1<<j)+1;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int RMQ(int l,int r){
if(l>r)return 0;
int k=b[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
int n,q,l,r;
initlog();
while(~scanf("%d",&n)&&n){
cin>>q;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i==1){ //初始化过程
f[i][0]=1;continue;
}
if(a[i]==a[i-1]){
f[i][0]=f[i-1][0]+1;
}
else f[i][0]=1;
}
ST(n);
for(int j=1;j<=q;j++){
scanf("%d%d",&l,&r);
int t=l;
while(t<=r&&a[t]==a[t-1]) t++;//将查询区间分开
printf("%d\n",max(t-l,RMQ(t,r)));
}
}
}