看完RMQ的课件，里面用了这题做例题，所以就试下用RMQ来解这题。
RMQ总算是看懂而且会用了。RMQ跟线段树有点相似，也是二分区间来快速求出最值。不过，线段树的适用范围明显更广，RMQ主要是用作离线查询区间最值的。然而居然推荐这题拿来做RMQ，还真让我不解.....不过也没关系，也可以做，就是query的时候显得有点麻烦罢了！
query的修改耗了我不少时间，因为RMQ查询的区间长度总是2的n次方，所以如果我的查询结果横跨两个区间，这时的操作就有点麻烦了。这时查询的复杂度升至O(log n)了。这个使用限制还是我一直找不到错误数据看了一下别人的题解才明白啊！也是因为这样，RMQ还是最好在Minimum/Maximum Query的时候用。
好难看的代码（RMQ版1200ms+）：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 const int maxn = 100005; 8 const int maxm = 17; 9 10 struct sec{ 11 int m; 12 int lv, ln; 13 int rv, rn; 14 void add(int a, int b, int c, int d, int e){ 15 m = a; 16 lv = b; ln = c; 17 rv = d; rn = e; 18 } 19 }s[maxn][maxm]; 20 int ep[maxm + 2]; 21 22 void pre(){ 23 ep[0] = 1; 24 for (int i = 1; i < maxm + 2; i++) 25 ep[i] = ep[i - 1] << 1; 26 #ifndef ONLINE_JUDGE 27 for (int i = 1; i < maxm + 2; i++) 28 printf("%d\n", ep[i]); 29 #endif 30 } 31 32 void scan(int &n){ 33 char ch; 34 35 while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); 36 if (ch != '-'){ 37 n = ch - '0'; 38 while ((ch = getchar()) >= '0' && ch <= '9') 39 n = n * 10 + ch - '0'; 40 } 41 else{ 42 n = 0; 43 while ((ch = getchar()) >= '0' && ch <= '9') 44 n = n * 10 + '0' - ch; 45 } 46 } 47 48 void initRMQ(int n){ 49 int tmp, ln, rn; 50 51 for (int j = 1; ep[j] <= n; j++){ 52 for (int i = 1; i + ep[j] <= n + 1; i++){ 53 if (s[i][j - 1].m > s[i + ep[j - 1]][j - 1].m) tmp = s[i][j - 1].m; 54 else tmp = s[i + ep[j - 1]][j - 1].m; 55 if (s[i][j - 1].rv == s[i + ep[j - 1]][j - 1].lv){ 56 if (tmp < s[i][j - 1].rn + s[i + ep[j - 1]][j - 1].ln) 57 tmp = s[i][j - 1].rn + s[i + ep[j - 1]][j - 1].ln; 58 } 59 if (s[i][j - 1].lv == s[i + ep[j - 1]][j - 1].lv) ln = ep[j - 1] + s[i + ep[j - 1]][j - 1].ln; 60 else ln = s[i][j - 1].ln; 61 if (s[i][j - 1].rv == s[i + ep[j - 1]][j - 1].rv) rn = ep[j - 1] + s[i][j - 1].rn; 62 else rn = s[i + ep[j - 1]][j - 1].rn; 63 s[i][j].add(tmp, s[i][j - 1].lv, ln, s[i + ep[j - 1]][j - 1].rv, rn); 64 } 65 } 66 } 67 68 int query(int l, int r){ 69 int len; 70 int ret, tmp; 71 72 len = (int)floor(log((double)r - l + 1) / log(2.0)); 73 #ifndef ONLINE_JUDGE 74 printf("len %d\n", len); 75 #endif 76 if (s[l][len].m > s[r - ep[len] + 1][len].m) ret = s[l][len].m; 77 else ret = s[r - ep[len] + 1][len].m; 78 tmp = s[l][len].rn; 79 while (s[l][len].rv == s[l + ep[len]][0].lv && l + ep[len] <= r){ 80 l += ep[len]; 81 len = (int)floor(log((double)r - l + 1) / log(2.0)); 82 #ifndef ONLINE_JUDGE 83 printf("len %d\n", len); 84 #endif 85 tmp += s[l][len].ln; 86 if (s[l][len].lv != s[l][len].rv || l >= r) break; 87 } 88 89 if (tmp > ret) return tmp; 90 else return ret; 91 } 92 93 void RMQ(int n){ 94 int m; 95 int x, y; 96 97 scan(m); 98 for (int i = 1; i <= n; i++){ 99 scan(x);100 //scanf("%d", &x);101 s[i][0].add(1, x, 1, x, 1);102 }103 104 initRMQ(n);105 for (int i = 0; i < m; i++){106 scan(x); scan(y);107 //scanf("%d%d", &x, &y);108 printf("%d\n", query(x, y));109 }110 }111 112 int main(){113 int n;114 #ifndef ONLINE_JUDGE115 freopen("in", "r", stdin);116 #endif117 pre();118 while (true){119 memset(s, 0, sizeof(s));120 scan(n);121 //scanf("%d", &n);122 if (!n) return 0;123 RMQ(n);124 }125 }
用线段树写：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 #define lson l, m, rt << 1 8 #define rson m + 1, r, (rt << 1) | 1 9 10 const int maxn = 100005; 11 struct seg{ 12 int m; 13 int lv; 14 int ln; 15 int rv; 16 int rn; 17 }; 18 int lv[maxn << 2], ln[maxn << 2], mx[maxn << 2], rv[maxn << 2], rn[maxn << 2]; 19 20 void init(int n){ 21 for (int i = 0; i <= n << 2; i++) 22 lv[i] = ln[i] = rv[i] = rn[i] = mx[i] = 0; 23 } 24 25 void scan(int &n){ 26 char ch; 27 28 while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); 29 if (ch != '-'){ 30 n = ch - '0'; 31 while ((ch = getchar()) >= '0' && ch <= '9') 32 n = n * 10 + ch - '0'; 33 } 34 else{ 35 n = 0; 36 while ((ch = getchar()) >= '0' && ch <= '9') 37 n = n * 10 + '0' - ch; 38 } 39 } 40 41 void up(int rt){ 42 int l = rt << 1; 43 int r = (rt << 1) | 1; 44 45 if (mx[l] > mx[r]) mx[rt] = mx[l]; 46 else mx[rt] = mx[r]; 47 if (rv[l] == lv[r]){ 48 if (mx[rt] < rn[l] + ln[r]) 49 mx[rt] = rn[l] + ln[r]; 50 } 51 lv[rt] = lv[l]; 52 rv[rt] = rv[r]; 53 if (lv[l] == lv[r]) ln[rt] = ln[l] + ln[r]; 54 else ln[rt] = ln[l]; 55 if (rv[r] == rv[l]) rn[rt] = rn[r] + rn[l]; 56 else rn[rt] = rn[r]; 57 } 58 59 void build(int l, int r, int rt){ 60 if (l == r){ 61 int x; 62 63 scan(x); 64 lv[rt] = rv[rt] = x; 65 mx[rt] = ln[rt] = rn[rt] = 1; 66 67 return ; 68 } 69 int m = (l + r) >> 1; 70 71 build(lson); 72 build(rson); 73 up(rt); 74 } 75 76 seg query(int L, int R, int l, int r, int rt){ 77 seg ret; 78 if (L <= l && r <= R){ 79 ret.m = mx[rt]; 80 ret.lv = lv[rt]; 81 ret.ln = ln[rt]; 82 ret.rv = rv[rt]; 83 ret.rn = rn[rt]; 84 #ifndef ONLINE_JUDGE 85 printf("%2d: %2d %2d %2d %2d %2d\n", rt, ret.m, ret.lv, ret.ln, ret.rv, ret.rn); 86 #endif 87 return ret; 88 } 89 90 seg rret; 91 int m = (l + r) >> 1; 92 93 if (L <= m){ 94 ret = query(L, R, lson); 95 if (m < R){ 96 rret = query(L, R, rson); 97 if (ret.m < rret.m) ret.m = rret.m; 98 if (ret.rv == rret.lv){ 99 if (ret.m < ret.rn + rret.ln)100 ret.m = ret.rn + rret.ln;101 }102 if (ret.lv == rret.lv) ret.ln += rret.ln;103 if (ret.rv == rret.rv) ret.rn += rret.rn;104 else ret.rn = rret.rn; // 开始的时候漏了这句，wa了好久..- -105 ret.rv = rret.rv;106 }107 }108 else if (m < R) ret = query(L, R, rson);109 #ifndef ONLINE_JUDGE110 printf("%2d: %2d %2d %2d %2d %2d\n", rt, ret.m, ret.lv, ret.ln, ret.rv, ret.rn);111 #endif112 113 return ret;114 }115 116 void deal(int n){117 int m;118 int x, y;119 120 init(n);121 scan(m);122 build(1, n, 1);123 #ifndef ONLINE_JUDGE124 for (int i = 0; i < (n << 2); i++)125 printf("%2d: %2d %2d %2d %2d %2d\n", i, mx[i], lv[i], ln[i], rv[i], rn[i]);126 puts("");127 #endif128 for (int i = 0; i < m; i++){129 scan(x); scan(y);130 printf("%d\n", query(x, y, 1, n, 1).m);131 }132 }133 134 int main(){135 int n;136 #ifndef ONLINE_JUDGE137 freopen("in", "r", stdin);138 #endif139 while (true){140 scan(n);141 if (!n) return 0;142 deal(n);143 }144 }
貌似写出来的代码也是要挺长的，而且这题的合并要注意，我就因为更新的时候漏了一丁点东西，测试了不下100组数据，测了我一个晚上才找出问题的根源....囧！ 以后要加倍注意线段树更新的严谨啊！
——written by Lyon