题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
在询问过程中账本的内容可能会被修改。
输入
输入中第一行有两个数m,n表示有m(m< =100000)笔账,n表示有n个问题，n<=100000。 接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y。当p=1，则查询[x,y]区间；当p=2，则改变第x个数为y。
输出
输出文件中为每个问题的答案。具体查看样例。
样例输入
10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10样例输出
2 0
这题显然可以用线段树解决，但是作为一道这么简单的题目，我们尝试一下其它的做法。
最近看了一下白书写的分桶法，就拿这题来试试效果怎样。
分桶法的时间复杂度一般是带根号的。
在这里，我用√n个桶，则每个桶里都有n/√n=√n个数值。
对于每次操作，时间复杂度为 O(√n)（至于为什么下面注释里会说）。
所以总的时间复杂度为 O(m*√n)。
#include <cstdio>
#include <cstring> //maxsqr既是桶的数量，也是每个桶里存的元素的数量
const int maxn=, maxsqr=; int n,m;
//a数组为该数的值
int a[maxn];
//bucket[i]表示第i个桶里的最小值
//即为a[i*maxsqr]~a[(i+1)*maxsqr-1]这个区间的最小值
int bucket[maxsqr]; int max(int x, int y) { return x>y?x:y; } int min(int x, int y) { return x<y?x:y; } void init() {
memset(bucket,0x7F,sizeof(bucket)); //对每个桶进行初始化 scanf("%d%d",&n,&m);
for (int i=; i<n; i++) {
scanf("%d",a+i);
//i号元素所在的桶的编号为i/maxsqr
bucket[i/maxsqr]=min(bucket[i/maxsqr],a[i]);
}
} //更新操作
void update(int x, int y) {
a[x]=y; //先单独更新数值
int t=x/maxsqr; //该数值所在的桶的编号 //把该数值所在的桶表示的区间再扫过一遍，重置最小值
//因为桶内不超过sqrt(n)个元素
//所以更新操作的时间复杂度为 O(sqrt(n))
bucket[t]=0x7F7F7F7F;
//特别注意，此处i<n是为了保证不访问到没有数值的区域
//如果访问到，一来会RE，二来那里的a[i]=0，桶内的最小值会错
for (int i=t*maxsqr; i<(t+)*maxsqr&&i<n; i++)
bucket[t]=min(bucket[t],a[i]);
} //查询操作
int query(int x, int y) {
int res=0x7F7F7F7F;
//左端所在的桶:t1, 右端所在的桶：t2
int t1=x/maxsqr, t2=y/maxsqr; //没有被完全覆盖在桶里的，也就是左右端所在的桶
//一个个扫过去，暴力求解最小值
//因为多出来的元素最多2*sqrt(n)个
//所以时间复杂度控制在 O(sqrt(n))
for (int i=x; i<(t1+)*maxsqr&&i<=y; i++)
res=min(res,a[i]);
for (int i=max(x,t2*maxsqr); i<=y; i++)
res=min(res,a[i]); //查询的区间完全覆盖了这些桶所保存的区间最小值
//则只要与已经存好的桶的最小值作比较就好了
//因为桶只有sqrt(n)个
//所以时间复杂度亦为 O(sqrt(n))
//这样，整个查询操作的复杂度就为 O(sqrt(n))
for (int i=t1+; i<t2; i++)
res=min(res,bucket[i]);
return res;
} int main() {
init();
for (int i=; i<=m; i++) {
int p,x,y;
scanf("%d%d%d",&p,&x,&y);
//因为数组是从0开始用的，所以表示下标的数都应该-1
if (p==)
update(x-,y);
else printf("%d ",query(x-,y-));
}
return ;
}