题目链接：?pid=119
解题思路：
RMQ算法。
不会的可以去看看我总结的RMQ算法。
代码如下：
#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const int N = 100010;int maxsum[N][20], minsum[N][20];void RMQ(int num) //预处理->O(nlogn){for(int j = 1; j < 20; ++j)for(int i = 1; i <= num; ++i)if(i + (1 << j) – 1 <= num){maxsum[i][j] = max(maxsum[i][j – 1], maxsum[i + (1 << (j – 1))][j – 1]);minsum[i][j] = min(minsum[i][j – 1], minsum[i + (1 << (j – 1))][j – 1]);}}int main(){int num, query;int src, des;scanf("%d %d", &num, &query);for(int i = 1; i <= num; ++i) //输入信息处理{scanf("%d", &maxsum[i][0]);minsum[i][0] = maxsum[i][0];}RMQ(num);while(query–) //O(1)查询{scanf("%d %d", &src, &des);int k = (int)(log(des – src + 1.0) / log(2.0));int maxres = max(maxsum[src][k], maxsum[des – (1 << k) + 1][k]);int minres = min(minsum[src][k], minsum[des – (1 << k) + 1][k]);printf("%d\n", maxres – minres);}return 0;}
代码优化后：
#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const int N = 100010;int maxsum[20][N], minsum[20][N]; //优化1void RMQ(int num) //预处理->O(nlogn){for(int i = 1; i != 20; ++i)for(int j = 1; j <= num; ++j)if(j + (1 << i) – 1 <= num){maxsum[i][j] = max(maxsum[i – 1][j], maxsum[i – 1][j + (1 << i >> 1)]); //优化2minsum[i][j] = min(minsum[i – 1][j], minsum[i – 1][j + (1 << i >> 1)]);}}int main(){int num, query;int src, des;scanf("%d %d", &num, &query);for(int i = 1; i <= num; ++i) //输入信息处理{scanf("%d", &maxsum[0][i]);minsum[0][i] = maxsum[0][i];}RMQ(num);while(query–) //O(1)查询{scanf("%d %d", &src, &des);int k = (int)(log(des – src + 1.0) / log(2.0));int maxres = max(maxsum[k][src], maxsum[k][des – (1 << k) + 1]);int minres = min(minsum[k][src], minsum[k][des – (1 << k) + 1]);printf("%d\n", maxres – minres);}return 0;}优化1：数组由F[N][20]变为F[20][N];
因为数组的地址为a + i + j，对应上面数组，我们需要先循环N的部分，所以
如果是第一种，，我们计算时因为i不断变化，我们就需要计算a + i + j
如果是第二种，我们计算时a + i不变,只需要改变j
优化2：
位运算
以后我会去到很多很繁华或苍凉，
