POJ 3264 RMQ Spare Table算法

今天下午大帝讲的,我以前也不懂,所以也就跟着学学了,把中间的那个状态转移方程学错了好几次,于是就wa了

好几发。

#include #include #include #define maxn 200010 using namespace std; int a[maxn],m,n,b[maxn],fl[maxn][50],fr[maxn][50]; void solve() { b[1]=0;//其实就是用来计算除以log2的值 for(int i=2;i=0;i--) for(int j=1;i+(1>a[i]; solve(); while(n--) { int u,v; cin>>u>>v; u--; v--; printf("%d\n",qma(u,v)-qmi(u,v)); } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:U - Count the Colors(成段更新+统计)
下一篇:hive按当天日期建立分区表 | 动态往日期分区插入数据
相关文章

利用C++实现哈夫曼算法

闲谈C++算法封装:穷举法

简单的C++冒泡排序算法代码

C++ 快速平方根算法实例代码

经典算法研究系列:十二、快速排序算法

堆排序算法,附图与C++代码

c++常见的算法快速分析解决(一)

c++常见的算法快速分析解决(二)

算法大全(c,c++)

[算法导论]c++实现计数排序

图文推荐
POJ 3264 RMQ Spare Table算法
ZOJ 3640 Help Me
POJ 3264 RMQ Spare Table算法
CF 518C(Anya and
POJ 3264 RMQ Spare Table算法
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-11-18 人气:3
本文关键词:
分享到:

相关文章

  • POJ 3264 Balanced Lineup 最基本的RMQ 2013-07-16

    其实这个题早就过了,只是当时为了偷懒拿线段树做的。当时肤浅的认为RMQ问题线段树都能胜任,现在才发现毕竟土洋。 不过线段树做多了,RMQ就显得很容易理解了。 其实RMQ很多算法,不过最通用的应属ST算法,总体思想就是一个很简单的dp。 以求区间最大值为例,数组dp[ i ][ j ]记录的是区间[ i , i + (1 也就是说是从第 i 个元素开始,连续的 (1 不难发现,dp[ i ][ 0 ] == num[ i ] (num为存储输入数据的数组)。 而连续的 (1 显然 区间[ i ,

  • [POJ 3264]Balanced Lineup(ST算法求RMQ) 2012-06-11

    Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous rang

  • poj-3264-Balanced Lineup-线段树-区域查询 2012-04-07

    区域查询操作。 ma[i]:i区间内的最大值 mi[i]:i区间内的最小值 #include #include #include #include #include using namespace std; #define INF 99999999 #define lmin 1 #define rmax n #define lson l,(l+r)/2,rtrr||r=r) { cl[rt]+=x; return; } // push_down(rt); update(ll,rr,x,lson)

  • POJ 3264 Balanced Lineup ST算法 2013-04-05

    ST算法即是sparse table算法,就是稀疏表的意思,就是利用二分法来划分一个表,划分为2的次方段,之后利用这个st表计算查询结果,可以使得预处理时间O(nlgn),而查询时间为O(1) ; 那么有人会有疑问,既然查询时间是O(1),那么为什么这个算法很多时候并不比线段树快多少,甚至根本没有快过呢? 因为其实查询时间为O(log(range)), range为查询区间的大小,因为要找到range二进制的最高位数,可以使用floor(log(range))的数学方法查找这个数,不过也是需要l

  • C++的一种业务分发方案(另类的工厂模式) 2012-02-16

    在C++中,传统的业务分发,总要写一大串的switch-case,而且每次增加新业务时,都要在原有的switch-case里加一个分支,这就违反了设计模式中的开放封闭原则, 以下这种方案,就完全去除了switch-case,每当要添加业务模块时,只要写一个TEST_MODULE(index, name)就可以了。 思路很简单,直接上代码: #include #include #include using namespace std; //业务模块,第一个参数是模块ID,第二个是模块名称 //用了

  • hdu-1166-敌兵布阵-线段树-单点更新,区域查询 2012-02-26

    线段树的单点更新,区域查询操作。 #include #include #include #include #include using namespace std; #define lmin 1 #define rmax n #define lson l,(l+r)/2,rtrr||r=r) { cl[rt]+=x; return; } // push_down(rt); update(ll,rr,x,lson); update(ll,rr,x,rson); push_up(rt); } int

  • zoj 3827 Information Entropy(2014牡丹江区域赛I题) 2014-01-15

    Information Entropy Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge Information Theory is one of the most popular courses in Marjar University. In this course, there is an important chapter about information entropy. Entropy is the average

  • uva10635Prince and Princess(LIS) 2014-02-02

    题目:uva10635Prince and Princess(LIS) 题目大意:求最长相同公共子序列。 解题思路:因为数据很大,62500不能用之前的那种求LIS的做法来做。可以将第一个路线的整数重新排个序(0...p),然后之后的那个路线因为要找相同的最长子序列,所以要将它原来的数字映射成第一条路线新的数字。这样之后就只需要找第二个路线的LIS就可以了。 nlog(n)的LIS算法: 普通的做法在查找的时候,需要for一遍找到比v【i】小的数。 用LIS数组来存放前i个数的最长LIS(top

  • poj3274--Gold Balanced Lineup(hash) 2014-02-16

    Gold Balanced Lineup Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 12334 Accepted: 3618 Description Farmer John's N cows (1 ≤ N ≤ 100,000) share many similarities. In fact, FJ has been able to narrow down the list of features shared by h

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.037 (s). 10 q(s)