TOJ--1114--rmq/线段树

嗯 表示rmq真的好伤我......

这题是 大神 噢 不对 那他的称呼和晓爷冲突了..

他的做法 真的很好.... 时间在toj 又是最短的...

关于 rmq  我想说 理解它 真的很有用....

我又要重新好好学一遍了..

下面附上他的代码：----内含详细注释  不清楚的 可以再下方留言告诉我 基本每天总会上号的---------

 

#include <stdio.h>

int counts[100000]; // 每组数据的重复出现的次数
int boundary[100000]; // 记录下相同数据第一次出现的下标
int num[100000];  // n个数据的值
int hash[100000];  // 数据所对应的编号
int maximum[100000][18];

int main() {
    int n, q, i, j, gnum, width, half, left, right, ans, freq, index;
    // 读取个数n
    while (scanf("%d", &n) && n) 
    {
        // 读取询问数q
        scanf("%d", &q);
        for (i = 0; i < n; i++) 
        {
            // 读取num[i]
            scanf("%d", num + i);
        }
        // gnum代表不同的数字的分组的总数
        gnum = 0;
        // 扫一遍每一个数
        for (i = 0; i < n; i++) 
        {
            // 如果这个是第一个数，或者这个数和前面一个不一样
            if (i == 0 || num[i] != num[i - 1]) 
            {
                // 添加一个分组，并且那个分组的计数为0
                counts[gnum++] = 0;
                // boundary[i] 表示的是跟第i个数所在的组的第一个数的下标
                // 因为i是所在组的第一个数，所以boundary[i] = i
                boundary[i] = i;
            }
            else 
            { 
                // 因为这个数和前面的数一样，所以boundary[i] 和左边的 boundary是一样的
                boundary[i] = boundary[i - 1];
            }
            // hash[i] 表示 当前的数的分组编号是gnum - 1
            hash[i] = gnum - 1;
            // 并且为那个分组的数目加上1个，这就是为什么刚刚counts要设置为0，在这里还会加上的   
            counts[gnum - 1]++;
        }
        // 下面的部分是展示如何正确使用rmq (Range maximum/minimum query)
        // 首先给出maximum[i][j]的定义
        // maximum[i][j] 等于下标从i开始往后面数2^j那么多元素中的最大的那个
        for (i = 0; i < gnum; i++) 
        {
            // 因为j=0，所以maximum[i][0]就是只有1个元素counts[i] 
            maximum[i][0] = counts[i];
        }
        // 从1开始枚举j，直到2^j已经超过counts数组大小为止
        for (j = 1; (1 << j) <= gnum; j++) 
        {
            // 考虑的连续的个数是2 ^ j
            width = 1 << j;
            // 个数的一半是 half
            half = width >> 1;
            // 从起点i=0开始枚举，直到从i开始到数组的结尾已经不足width那么多个数为止
            for (i = 0; i + width <= gnum; i++) 
            {
                // 从i到i+half-1的最大值是left
                left = maximum[i][j - 1];
                // 从i+half到i+width-1的最大值是right
                right = maximum[i + half][j - 1];
                // 那么从i到i+width-1的最大值是left和right中比较大的那个
                maximum[i][j] = left > right ? left : right;
            }
        }
        // q个询问
        while (q--) 
        { 
            // 读取左右
            scanf("%d%d", &left, &right);
            // 换成 0 下标
            left--;
            right--;
            // 如果左右的hash一样，说明中间的数都是同一个
            if (hash[left] == hash[right])   // hash值相同 证明在同一个分组 即数据相同
            {
                // 答案就是区间长度
                printf("%d\n", right - left + 1);
                continue;
            }
            // freq 是我们要记录的最大频次
            // 对于 left 来说，我们并不能取的所有的数，所以我们快捷的计算一下left的个数
            // left的个数等于left所在的组的总个数 + left离改组第一个数的距离
            // 这个可能有点难想象，不过把端点情况枚举一下就可以知道了
            // 当left和boundary[left]一样的时候，个数就是counts[hash[left]]
            // 随着left增大，个数递减，所以left前面是负号
            freq = counts[hash[left]] + boundary[left] - left;// 其实这个式子还是蛮容易看懂的....
            // right所在的个数，如果right和boundary[right]一样，那么就只有1个
            // 因为随着right递增，个数增加，所以right前面是正号
            if (right - boundary[right] + 1 > freq) //虽然和上面求left的个数有点区别 但还是手动模拟就可以知道
            {
                // 如果right的freq比较大，更新freq
                freq = right - boundary[right] + 1;
            }
            // left 替换为left所在组下一个组的组坐标
            left = hash[left] + 1; // 
            // right 替换为right所在组的前一个组的坐标
            right = hash[right] - 1;
            // left <= right 就是说中间还有别的组
            if (left <= right) {
            
                // 中间组的个数是width
                width = right - left + 1;
                
                // 现在我们要查找的就是counts[left]到counts[right]中的最大值
                // 这里有问题吗，要查询的东西
                j = 0;
                // 这里我们需要一个j, 使得2^j的两倍不少于width，且2^j不大于width
                //所以只要2^(j+1) < width, 我们就增加j
                while ( (1 << (j + 1) ) < width ) j++;
                // int j = (int)(log(v-s+1.0)/log(2.0)); 这样也可以 但是上面的更直观
                // 这里查询的是 counts[left] 到 counts[left + 2^j - 1] 中的最大值
                index = maximum[left][j];
                if (freq < index ) 
                {
                    freq = index;
                }
                // 这里查询的是counts[right - 2^j + 1] 到 counts[right] 中的最大值
                index = maximum[right - (1 << j) + 1][j];
                if (freq < index) 
                {
                    freq = index;
                }
                // 到这里你应该明白rmq是怎么一回事了
                // 上面的区间有这样一个特性
                // 第一个区间是从left开始，长度为2^j, 第二个区间以right结束，长度为2^j
                // 因为长度是2^j, 所以我们之前都已经算好了，这里直接拿来用
                // 而且因为2^j的两倍，至少有width那么大，所以必定能覆盖left到right的所有元素
                // 而且2^j 不超过width，所以也不用担心会超过边界
                // 左右两个长度为2^j的分区的最大值中的最大值，则必定是整个区间的最大值
            }
            printf("%d\n", freq);
        }
    }
    return 0;
}

 

today:

　　我说了所有的谎 你全都相信

　　简单的我爱你 你却老不信