http://acm.hdu.edu.cn/showproblem.php?pid=1806
线段树维护区间出现频率最高的出现次数。为了维护上者，需要维护线段前后缀的出现次数，当和其他线段在端点处的字符相等时，要做合并处理。
#include <iostream> #include <cstdlib> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <map> using namespace std; int n, m; const int len = 100005; int num[len]; struct node { int l, r; int ll, rr; int v; }; node tr[len << 2]; void pushUp(int rt) { tr[rt].v = max(tr[rt << 1].v, tr[rt << 1 | 1].v); if (num[tr[rt << 1].r] == num[tr[rt << 1 | 1].l]) tr[rt].v = max(tr[rt].v, tr[rt << 1].rr + tr[rt << 1 | 1].ll); tr[rt].ll = tr[rt << 1].ll; tr[rt].rr = tr[rt << 1 | 1].rr; if (num[tr[rt].l] == num[tr[rt << 1 | 1].l]) tr[rt].ll += tr[rt << 1 | 1].ll; if (num[tr[rt].r] == num[tr[rt << 1].r]) tr[rt].rr += tr[rt << 1].rr; } void build(int l, int r, int rt) { tr[rt].l = l; tr[rt].r = r; if (l == r) { tr[rt].v = 1; tr[rt].ll = tr[rt].rr = 1; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1|1); pushUp(rt); } int query(int l, int r, int rt) { if (l <= tr[rt].l&&tr[rt].r <= r) return tr[rt].v; int mid = (tr[rt].l + tr[rt].r) >> 1; int lr=-1, rr=-1; if (l <= mid) lr = query(l, r, rt << 1); if (r > mid) rr = query(l, r, rt << 1 | 1); int ans = max(lr, rr); if (lr != -1 && rr != -1&&num[mid]==num[mid+1]) { ans = max(ans, min(tr[rt << 1].rr,mid-l+1) + min(r-mid,tr[rt << 1 | 1].ll)); } //if (ans == 4) cout << tr[rt].l << ' ' << tr[rt].r<<' '<<lr<<' '<<rr<< endl; return ans; } int main() { while (scanf("%d", &n) != EOF) { if (n == 0) break; scanf("%d", &m); for (int i = 1; i <= n; i++) scanf("%d", &num[i]); build(1, n, 1); while (m--) { int l, r; scanf("%d%d", &l , &r); printf("%d ", query(l, r, 1)); } } return 0; }