ST算法

Time Limit: 1000 ms   Case Time Limit: 1000 ms   Memory Limit: 64 MB Total Submission: 672   Submission Accepted: 126 Description 给出N个数，求第a个数到第b个数之间最大的数减去最小的数的结果 Input N（N小于100,000），M（M小于100,000） 接下来有N个数 接下来M组范围,所有数均在[0,2 ³¹-1]内 每个范围有2个整数a,b(1<=a<=b<=N) Output 每行输出一个结果 Sample Input OriginalTransformed 5 3 4 2 5 1 10 1 5 2 3 2 2 5[SP]3[EOL]  4[SP]2[SP]5[SP]1[SP]10[EOL]  1[SP]5[EOL]  2[SP]3[EOL]  2[SP]2[EOF]  Sample Output OriginalTransformed

930

#include<cstdio> #include<cmath> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<queue> //#define DEBUG const int maxn = 100005; int Max[maxn][17]; int Min[maxn][17]; int num[maxn]; int pow(int a, int n); using namespace std; int main() { #ifdef DEBUG freopen("Text.txt", "r", stdin); #endif // DEBUG cin.tie(0); cin.sync_with_stdio(false); int n, m; cin >> n >> m; int i, j; for (i = 1; i <= n; i++) cin >> num[i]; for (j = 0; pow(2, j) <= n; j++) { for (i = 1;i + pow(2, j) - 1<= n; i++) { if (j == 0) Min[i][j] = Max[i][j] = num[i]; else { Max[i][j] = max(Max[i][j - 1], Max[i + pow(2, j - 1)][j - 1]); Min[i][j] = min(Min[i][j - 1], Min[i + pow(2, j - 1)][j - 1]); } } } int bit, a, b; for (i = 1; i <= m;i++) { cin >> a >> b; bit = (int)(log(b - a + 1.0) / log(2.0)); //cout << max(Max[a][bit], Max[b - pow(2, bit) + 1][bit]) << ends; //cout << min(Min[a][bit], Min[b - pow(2, bit) + 1][bit]) << endl; cout << max(Max[a][bit], Max[b - pow(2, bit) + 1][bit]) - min(Min[a][bit], Min[b - pow(2, bit) + 1][bit]) <<endl; } } int pow(int a, int n) { if (a == 1) return 1; if (a == 2) return 1 << n; int i, copy = 1; for (i = 1; i <= n; i++) copy = copy*a; return copy; }