这道题可以用ST表过：

题目链接

记录4个数组：maxval[][], minval[][], ans[][], rans[][]

maxval[i][j]表示从i号元素开始，长度为(1<<j)（也就是2^j）的区间上的最大值

minval[i][j]表示从i号元素开始，长度为(1<<j)的区间上的最小值

ans[i][j]表示从i号元素开始，长度为(1<<j)的区间从左往右方向的答案

rans[i][j]表示从i号元素开始，长度为(1<<j)的区间从右往左方向的答案

那么易得如下转移方程：

maxval[i][j] = max(maxval[i][j - 1], maxval[i + (1 << (j - 1))][j - 1])

minval差不多

对于ans和rans的转移，我们这样考虑

区间[l, r]上的答案，要么是区间[l, (l+r)/2]上的答案，要么是区间[(l+r)/2+1, r]上的答案，要么是[(l+r)/2+1, r]上的最大值减去[l, (l+r)/2]上的最小值，以上三者中取最大者

ans[i][j] = max(ans[i][j - 1], ans[i + (1 << (j - 1))][j - 1], maxval[i + (1 << (j - 1))][j - 1] - minval[i][j - 1]);

rans差不多

在预处理的时候，要把j的循环提到外层，因为[l, r]的状态需要用到[(l+r)/2+1, r]的状态转移而来

如果j的循环在内层的话，求解[l, r]的状态时[(l+r)/2+1, r]的状态还没有求解过

查询的过程应该比较好理解，直接看代码吧

#include <algorithm>

#include <cmath>

#include <iostream>

using std::cin;

using std::cout;

using std::endl;

using std::max;

using std::min;

template <typename T>

inline const T &max(const T &a, const T &b, const T &c)

{

     return max(a, max(b, c));

}

const double LOG2 = std::log(2);

int a[200010];

int maxval[200010][50];

int minval[200010][50];

int ans[200010][50];

int rans[200010][50];

int n, m;

inline void stInit()

{

     for (int i = 1; i <= n; ++i)

         minval[i][0] = maxval[i][0] = a[i];

     for (int j = 1; 1 << j <= n; ++j)

         for (int i = 1; i + (1 << j) - 1 <= n; ++i)

         {

         minval[i][j] = min(minval[i][j - 1], minval[i + (1 << (j - 1))][j - 1]);

         maxval[i][j] = max(maxval[i][j - 1], maxval[i + (1 << (j - 1))][j - 1]);

         ans[i][j] = max(ans[i][j - 1], ans[i + (1 << (j - 1))][j - 1],

         maxval[i + (1 << (j - 1))][j - 1] - minval[i][j - 1]);

         rans[i][j] = max(rans[i][j - 1], rans[i + (1 << (j - 1))][j - 1],

         maxval[i][j - 1] - minval[i + (1 << (j - 1))][j - 1]);

         }

}

inline int queryMax(int l, int r)

{

     int k = static_cast<int>(std::log(r - l + 1) / LOG2);

     return max(maxval[l][k], maxval[r - (1 << k) + 1][k]);

}

inline int queryMin(int l, int r)

{

     int k = static_cast<int>(std::log(r - l + 1) / LOG2);

     return min(minval[l][k], minval[r - (1 << k) + 1][k]);

}

inline int queryAns(int l, int r)

{

     int k = static_cast<int>(std::log(r - l + 1) / LOG2);

     if (l + (1 << k) > r)

         return max(ans[l][k], ans[r - (1 << k) + 1][k]);

     else

         return max(ans[l][k], ans[r - (1 << k) + 1][k],

                         queryMax(l + (1 << k), r) - queryMin(l, r - (1 << k)));

}

inline int queryRans(int l, int r)

{

     int k = static_cast<int>(std::log(r - l + 1) / LOG2);

     if (l + (1 << k) > r)

         return max(rans[l][k], rans[r - (1 << k) + 1][k]);

     else

         return max(rans[l][k], rans[r - (1 << k) + 1][k],

                         queryMax(l, r - (1 << k)) - queryMin(l + (1 << k), r));

}

int main()

{

     cin >> n;

     for (int i = 1; i <= n; ++i)

         cin >> a[i];

     stInit();

     cin >> m;

     while (m--)

     {

     int l, r;

     cin >> l >> r;

     if (l < r)

         cout << queryAns(l, r) << endl;

     else if (l > r)

         cout << queryRans(r, l) << endl;

     else

         cout << 0 << endl;

     }

     return 0;

}

不难看出，查询的时间复杂度是O(1)的，预处理的时间复杂度是O(nlogn)的

巴特西

codevs 3304 水果姐逛水果街Ⅰ

这道题可以用ST表过：

题目链接

记录4个数组：maxval[][], minval[][], ans[][], rans[][]

maxval[i][j]表示从i号元素开始，长度为(1<<j)（也就是2^j）的区间上的最大值

minval[i][j]表示从i号元素开始，长度为(1<<j)的区间上的最小值

ans[i][j]表示从i号元素开始，长度为(1<<j)的区间从左往右方向的答案

rans[i][j]表示从i号元素开始，长度为(1<<j)的区间从右往左方向的答案

那么易得如下转移方程：

maxval[i][j] = max(maxval[i][j - 1], maxval[i + (1 << (j - 1))][j - 1])

minval差不多

对于ans和rans的转移，我们这样考虑

区间[l, r]上的答案，要么是区间[l, (l+r)/2]上的答案，要么是区间[(l+r)/2+1, r]上的答案，要么是[(l+r)/2+1, r]上的最大值减去[l, (l+r)/2]上的最小值，以上三者中取最大者

ans[i][j] = max(ans[i][j - 1], ans[i + (1 << (j - 1))][j - 1], maxval[i + (1 << (j - 1))][j - 1] - minval[i][j - 1]);

rans差不多

在预处理的时候，要把j的循环提到外层，因为[l, r]的状态需要用到[(l+r)/2+1, r]的状态转移而来

如果j的循环在内层的话，求解[l, r]的状态时[(l+r)/2+1, r]的状态还没有求解过

查询的过程应该比较好理解，直接看代码吧

不难看出，查询的时间复杂度是O(1)的，预处理的时间复杂度是O(nlogn)的

最新文章

热门文章