TYVJ P1039 【忠诚2】

这题显然可以用线段树解决，但是作为一道这么简单的题目，我们尝试一下其它的做法。

最近看了一下白书写的分桶法，就拿这题来试试效果怎样。

分桶法的时间复杂度一般是带根号的。

在这里，我用√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 ;

 }