hihoCoder#1070 RMQ问题再临

模拟题，naive算法即可过，想着顺便练习一下ST吧，结果还超时了。。。

看来ST真不适合处理动态修改的问题，连naive算法的效率都不如。

超时的ST代码：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 #define MAX_NODE 10008
 6 
 7 int N, Q;
 8 int st[MAX_NODE][32];
 9 
10 void build() {
11   for (int j = 1; (1 << j) <= N; j++)
12     for (int i = 0; i + (1 << j) <= N; i++)
13       st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
14 }
15 
16 int query(int l, int r) {
17   int len = r - l + 1;
18   int i = 0;
19   while ((1 << (i + 1)) <= len)
20     i++;
21   return min(st[l][i], st[r - (1 << i) + 1][i]);
22 }
23 
24 void update(int p, int v) {
25   st[p][0] = v;
26   for (int j = 1; p + (1 << j) - 1 <= N || p - (1 << j) + 1 >= 0; j++)
27     for (int i = max(p - (1 << j) + 1, 0); i + (1 << j) - 1 <= N; i++) {
28       st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
29     }
30 }
31 
32 int main() {
33   scanf("%d", &N);
34   for (int i = 0; i < N; i++)
35     scanf("%d", &(st[i][0]));
36 
37   build();
38 
39   scanf("%d", &Q);
40   while (Q--) {
41     int t, a, b;
42     scanf("%d%d%d", &t, &a, &b);
43     if (!t)
44       printf("%d
", query(a - 1, b - 1));
45     else
46       update(a - 1, b);
47   }
48 
49   return 0;
50 }

Naive代码：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 #define MAX_NODE 10008
 6 
 7 int N, Q;
 8 int w[MAX_NODE];
 9 
10 int query(int l, int r) {
11   int res = w[l];
12   for (int i = l; i <= r; i++) {
13     res = min(res, w[i]);
14   }
15   return res;
16 }
17 
18 void update(int p, int v) {
19   w[p] = v;
20 }
21 
22 int main() {
23   scanf("%d", &N);
24   for (int i = 0; i < N; i++)
25     scanf("%d", &(w[i]));
26 
27   scanf("%d", &Q);
28   while (Q--) {
29     int t, a, b;
30     scanf("%d%d%d", &t, &a, &b);
31     if (!t)
32       printf("%d
", query(a - 1, b - 1));
33     else
34       update(a - 1, b);
35   }
36 }