文字解释见 http://hi.baidu.com/lewutian/blog/item/d0e058ea85b780d8d539c9bf.html
/* ID: sdj22251 PROG: subset LANG: C++ */ #include <iostream> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cmath> #include <ctime> #define MAXN 111111 #define MAXM 104444 #define INF 100000000 #define PI acos(-1.0) #define eps 1e-12 #define L(X) X<<1 #define R(X) X<<1|1 using namespace std; struct PP { int left, right, num; }p[MAXN]; struct node { int left, right, mid; int mx; }tree[4 * MAXN]; int v[MAXN], h[MAXN]; int n, m, len; void get() { len = 1; p[1].left = 1; p[1].num = 1; h[1] = 1; for(int i = 2; i <= n; i++) { if(v[i] == v[i - 1]) p[len].num++; else { p[len++].right = i - 1; p[len].left = i; p[len].num = 1; } h[i] = len; } p[len].right = n; } void up(int C) { tree[C].mx = max(tree[L(C)].mx, tree[R(C)].mx); } void make_tree(int s, int e, int C) { tree[C].left = s; tree[C].right = e; tree[C].mid = (s + e) >> 1; if(s == e){tree[C].mx = p[s].num; return;} make_tree(s, tree[C].mid, L(C)); make_tree(tree[C].mid + 1, e, R(C)); up(C); } int query(int s, int e, int C) { if(tree[C].left >= s && tree[C].right <= e) return tree[C].mx; int ret = 0; if(tree[C].mid >= s) {int t = query(s, e, L(C)); ret = max(ret, t);} if(tree[C].mid < e) {int t = query(s, e, R(C)); ret = max(ret, t);} return ret; } int in() { int flag = 1; char ch; int a = 0; while((ch = getchar()) == ' ' || ch == '\n'); if(ch == '-') flag = -1; else a += ch - '0'; while((ch = getchar()) != ' ' && ch != '\n') { a *= 10; a += ch - '0'; } return flag * a; } void out(int a) { if(a < 0) {putchar('-'); a = -a;} if(a >= 10)out(a / 10); putchar(a % 10 + '0'); } int main() { while(scanf("%d", &n) != EOF && n) { scanf("%d", &m); for(int i = 1; i <= n; i++) v[i] = in(); get(); make_tree(1, len, 1); for(int i = 1; i <= m; i++) { int x, y; x= in(); y = in(); int u = h[x]; int v = h[y]; if(u == v) out(y - x + 1); else if(u == v - 1) out(max(p[u].right - x + 1, y - p[v].left + 1)); else { int ans = max(p[u].right - x + 1, y - p[v].left + 1); int t = query(u + 1, v - 1, 1); ans = max(ans, t); out(ans); } putchar('\n'); } } return 0; }