TYVJ P1039 【忠诚2】

题目描述

老管家是一个聪明能干的人。他为财主工作了整整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=100000, maxsqr=400;

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=0; 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+1)*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+1)*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+1; i<t2; i++)
        res=min(res,bucket[i]);
    return res;
}

int main() {
    init();
    for (int i=1; i<=m; i++) {
        int p,x,y;
        scanf("%d%d%d",&p,&x,&y);
        //因为数组是从0开始用的，所以表示下标的数都应该-1 
        if (p==2)
            update(x-1,y);
        else printf("%d ",query(x-1,y-1));
    }
    return 0;
}