POJ-3264 RMQ

题目链接：http://poj.org/problem?id=3264

参考博客链接：https://blog.csdn.net/qq_31759205/article/details/75008659

理解：题意求给定区域内最值之差。数据太大，暴力是行不通的，首先想到的是线段树，但RMQ实行和理解起来更简洁，就以新学的算法来写啦，所以等下细记录RMQ代码，略记录线段树代码，反正我的博客我做主，也就我一个人看。

以下是线段树解法：

 1 #include
 2 #include
 3 #include
 4 #define maxn 50005
 5 int a[maxn],treemax[maxn<<2],treemin[maxn<<2];//最大值和最小值树； 
 6 using namespace std;
 7 
 8 int max(int a,int b)
 9 {
10     return a>b?a:b;
11 }
12 
13 int min(int a,int b)
14 {
15     return a>b?b:a;
16 }
17 
18 void build(int l,int r,int n)
19 {
20     if(l==r)
21     {
22         treemax[n]=a[l];
23         treemin[n]=a[l];
24         return;
25     }
26     int mid=(l+r)>>1;
27     build(l,mid,n<<1);
28     build(mid+1,r,n<<1|1);
29     treemax[n]=max(treemax[n<<1],treemax[n<<1|1]);
30     treemin[n]=min(treemin[n<<1],treemin[n<<1|1]);
31 }//同时建立最大值最小值树； 
32 
33 int searchmax(int L,int R,int l,int r,int n)
34 {
35     if(l>=L&&r<=R)
36     return treemax[n];
37     int mid=(l+r)>>1,ans=-1;
38     if(L<=mid)
39     ans=max(ans,searchmax(L,R,l,mid,n<<1));
40     if(mid=L&&r<=R)
48     return treemin[n];
49     int mid=(l+r)>>1,ans=5000000;
50     if(L<=mid)
51     ans=min(ans,searchmin(L,R,l,mid,n<<1));
52     if(mid

对于RMQ，用了dp，用于解决区间最值问题很不错吧，只能感叹发明这算法的人厉害了，dp[i][j]的意思是对于第i个数，往后2的j次方个数里的最值是多少。先理清思路吧：
1：状态转移方程可运用性：F[i, j]=max（F[i，j-1], F[i + 2^(j-1)，j-1]）；因为对于每个dp所储存2^j范围的最值，都可以通过比较两段连续2^j-1范围的最值得到，第一段为以数i，范围j-1，即F[i,j-1],另一段为以数i+2^(j-1)（原数加原范围的一半），范围j-1，即F[i + 2^(j-1)，j-1];
2：查找可确定性：dp范围虽然是2^n，但可以实现任意区间的比较，利用了区间重复比较（即任意区间的表示都可以利用两个区间的并集来代替）：比如区间（1,5）可以由（1,4）和（2,5）两个区间代替，这里就涉及到了代码中k值的计算（2^k因小于等于区间长度）。
现在原理弄明白了（参考博客里有大牛解释），就上代码吧：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define maxn 50005
 6 int a[maxn],dpmax[maxn][20],dpmin[maxn][20];//最大值和最小值背包； 
 7 using namespace std;
 8 int max(int a,int b)
 9 {
10     return a>b?a:b;
11 }
12 
13 int min(int a,int b)
14 {
15     return a>b?b:a;
16 }
17 
18 int search(int index,int left,int right)//index为1，表示要返回区间最大值，其他为最小值； 
19 {
20     int k=0;
21     while((1<<(k+1))<=right-left+1) k++;//求k值，即所求的的范围2^k所不能超过，这样才能通过用两个比范围 小一级的范围代替； 
22     if(index==1) 
23     return max(dpmax[left][k],dpmax[right-(1<

总的就这样了；这题测试数据量很大，用cin会超时，还是老老实实用sp吧。