【算法每日一练]-结构优化（保姆级教程 篇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)));
		}
	}
}