TOJ--1114--rmq/线段树

2023-10-17 16:10
文章标签 线段 rmq 1114 toj

本文主要是介绍TOJ--1114--rmq/线段树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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

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

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

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

 

  1 #include <stdio.h>
  2 
  3 int counts[100000]; // 每组数据的重复出现的次数
  4 int boundary[100000]; // 记录下相同数据第一次出现的下标
  5 int num[100000];  // n个数据的值
  6 int hash[100000];  // 数据所对应的编号
  7 int maximum[100000][18];
  8 
  9 int main() {
 10     int n, q, i, j, gnum, width, half, left, right, ans, freq, index;
 11     // 读取个数n
 12     while (scanf("%d", &n) && n) 
 13     {
 14         // 读取询问数q
 15         scanf("%d", &q);
 16         for (i = 0; i < n; i++) 
 17         {
 18             // 读取num[i]
 19             scanf("%d", num + i);
 20         }
 21         // gnum代表不同的数字的分组的总数
 22         gnum = 0;
 23         // 扫一遍每一个数
 24         for (i = 0; i < n; i++) 
 25         {
 26             // 如果这个是第一个数,或者这个数和前面一个不一样
 27             if (i == 0 || num[i] != num[i - 1]) 
 28             {
 29                 // 添加一个分组,并且那个分组的计数为0
 30                 counts[gnum++] = 0;
 31                 // boundary[i] 表示的是跟第i个数所在的组的第一个数的下标
 32                 // 因为i是所在组的第一个数,所以boundary[i] = i
 33                 boundary[i] = i;
 34             }
 35             else 
 36             { 
 37                 // 因为这个数和前面的数一样,所以boundary[i] 和左边的 boundary是一样的
 38                 boundary[i] = boundary[i - 1];
 39             }
 40             // hash[i] 表示 当前的数的分组编号是gnum - 1
 41             hash[i] = gnum - 1;
 42             // 并且为那个分组的数目加上1个,这就是为什么刚刚counts要设置为0,在这里还会加上的   
 43             counts[gnum - 1]++;
 44         }
 45         // 下面的部分是展示如何正确使用rmq (Range maximum/minimum query)
 46         // 首先给出maximum[i][j]的定义
 47         // maximum[i][j] 等于下标从i开始往后面数2^j那么多元素中的最大的那个
 48         for (i = 0; i < gnum; i++) 
 49         {
 50             // 因为j=0,所以maximum[i][0]就是只有1个元素counts[i] 
 51             maximum[i][0] = counts[i];
 52         }
 53         // 从1开始枚举j,直到2^j已经超过counts数组大小为止
 54         for (j = 1; (1 << j) <= gnum; j++) 
 55         {
 56             // 考虑的连续的个数是2 ^ j
 57             width = 1 << j;
 58             // 个数的一半是 half
 59             half = width >> 1;
 60             // 从起点i=0开始枚举,直到从i开始到数组的结尾已经不足width那么多个数为止
 61             for (i = 0; i + width <= gnum; i++) 
 62             {
 63                 // 从i到i+half-1的最大值是left
 64                 left = maximum[i][j - 1];
 65                 // 从i+half到i+width-1的最大值是right
 66                 right = maximum[i + half][j - 1];
 67                 // 那么从i到i+width-1的最大值是left和right中比较大的那个
 68                 maximum[i][j] = left > right ? left : right;
 69             }
 70         }
 71         // q个询问
 72         while (q--) 
 73         { 
 74             // 读取左右
 75             scanf("%d%d", &left, &right);
 76             // 换成 0 下标
 77             left--;
 78             right--;
 79             // 如果左右的hash一样,说明中间的数都是同一个
 80             if (hash[left] == hash[right])   // hash值相同 证明在同一个分组 即数据相同
 81             {
 82                 // 答案就是区间长度
 83                 printf("%d\n", right - left + 1);
 84                 continue;
 85             }
 86             // freq 是我们要记录的最大频次
 87             // 对于 left 来说,我们并不能取的所有的数,所以我们快捷的计算一下left的个数
 88             // left的个数等于left所在的组的总个数 + left离改组第一个数的距离
 89             // 这个可能有点难想象,不过把端点情况枚举一下就可以知道了
 90             // 当left和boundary[left]一样的时候,个数就是counts[hash[left]]
 91             // 随着left增大,个数递减,所以left前面是负号
 92             freq = counts[hash[left]] + boundary[left] - left;// 其实这个式子还是蛮容易看懂的....
 93             // right所在的个数,如果right和boundary[right]一样,那么就只有1个
 94             // 因为随着right递增,个数增加,所以right前面是正号
 95             if (right - boundary[right] + 1 > freq) //虽然和上面求left的个数有点区别 但还是手动模拟就可以知道
 96             {
 97                 // 如果right的freq比较大,更新freq
 98                 freq = right - boundary[right] + 1;
 99             }
100             // left 替换为left所在组下一个组的组坐标
101             left = hash[left] + 1; // 
102             // right 替换为right所在组的前一个组的坐标
103             right = hash[right] - 1;
104             // left <= right 就是说中间还有别的组
105             if (left <= right) {
106             
107                 // 中间组的个数是width
108                 width = right - left + 1;
109                 
110                 // 现在我们要查找的就是counts[left]到counts[right]中的最大值
111                 // 这里有问题吗,要查询的东西
112                 j = 0;
113                 // 这里我们需要一个j, 使得2^j的两倍不少于width,且2^j不大于width
114                 //所以只要2^(j+1) < width, 我们就增加j
115                 while ( (1 << (j + 1) ) < width ) j++;
116                 // int j = (int)(log(v-s+1.0)/log(2.0)); 这样也可以 但是上面的更直观
117                 // 这里查询的是 counts[left] 到 counts[left + 2^j - 1] 中的最大值
118                 index = maximum[left][j];
119                 if (freq < index ) 
120                 {
121                     freq = index;
122                 }
123                 // 这里查询的是counts[right - 2^j + 1] 到 counts[right] 中的最大值
124                 index = maximum[right - (1 << j) + 1][j];
125                 if (freq < index) 
126                 {
127                     freq = index;
128                 }
129                 // 到这里你应该明白rmq是怎么一回事了
130                 // 上面的区间有这样一个特性
131                 // 第一个区间是从left开始,长度为2^j, 第二个区间以right结束,长度为2^j
132                 // 因为长度是2^j, 所以我们之前都已经算好了,这里直接拿来用
133                 // 而且因为2^j的两倍,至少有width那么大,所以必定能覆盖left到right的所有元素
134                 // 而且2^j 不超过width,所以也不用担心会超过边界
135                 // 左右两个长度为2^j的分区的最大值中的最大值,则必定是整个区间的最大值
136             }
137             printf("%d\n", freq);
138         }
139     }
140     return 0;
141 }
View Code

 

today:

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

  简单的我爱你 你却老不信

 

转载于:https://www.cnblogs.com/radical/p/3783320.html

这篇关于TOJ--1114--rmq/线段树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/226487

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

圆与线段的交点

poj 3819  给出一条线段的两个端点,再给出n个圆,求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 : 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ; 将点带入圆的方程即可。  注意: 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja