题意：给出q次询问，求区间内最长的连续序列。 水题。
1.RMQ 求法 ，st算法 2.线段树，简单的区间合并
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 111111; const int INF = 99999999; int Hash[maxn * 2]; int dp[maxn][20]; int ans; int sum[maxn]; void init() { for (int i = 0; i < ans; i++) dp[i][0] = sum[i]; for (int j = 1; (1 << j) <= ans; j++){ for (int i = 0; i + (1 << j) - 1 < ans; i++){ dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]); } } } int ask(int l, int r) { int k = 0; while ((1 << (k + 1)) <= r - l + 1) k++; return max(dp[l][k], dp[r + 1 - (1 << k)][k]); } int erfen(int a[], int key) { int pos = -1; int l = 0; int r = ans - 1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] <= key){ pos = mid; l = mid + 1; } else r = mid - 1; } return pos; } int erfen1(int a[], int key) { int pos = -1; int l = 0; int r = ans - 1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] >= key){ pos = mid; r = mid - 1; } else l = mid + 1; } return pos; } int main() { int n, q; int Begin[maxn], End[maxn]; int l, r; int a[maxn]; while (scanf("%d", &n), n){ scanf("%d", &q); for (int i = 0; i < n; i++) scanf("%d", &a[i]); a[n] = -INF; int start = 0; ans = 0; for (int i = 0; i < n; i++){ Hash[i] = ans; if (a[i] != a[i + 1]){ sum[ans] = i - start + 1; Begin[ans] = start; End[ans] = i; start = i + 1; ans++; } } init(); for (int i = 0; i < q; i++){ int ret = 0; scanf("%d%d", &l, &r); l--; r--; if (Hash[l] == Hash[r]){ printf("%d ", r - l + 1); continue; } int lpos = Begin[Hash[l] + 1]; int rpos = End[Hash[r] - 1]; ret = max(ret, lpos - l); ret = max(ret, r - rpos); if (Hash[l] + 1 == Hash[r]){ printf("%d ", ret); continue; } ret = max(ret, ask(Hash[l] + 1, Hash[r] - 1)); cout << ret << endl; } } return 0; }
线段树
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include <math.h> using namespace std; typedef long long LL; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 const int maxn = 111111; int a[maxn]; int sum[maxn << 2], lsum[maxn << 2], rsum[maxn << 2]; void up(int l, int r, int rt) { lsum[rt] = lsum[rt << 1]; rsum[rt] = rsum[rt << 1 | 1]; sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]); int mid = (l + r) >> 1; int len = (r - l + 1); if (lsum[rt] == (len - (len >> 1))) if (a[mid] == a[mid + 1]) lsum[rt] += lsum[rt << 1 | 1]; if (rsum[rt] == (len >> 1)) if (a[mid] == a[mid + 1]) rsum[rt] += rsum[rt << 1]; if (a[mid] == a[mid + 1]) sum[rt] = max(sum[rt], rsum[rt << 1] + lsum[rt << 1 | 1]); sum[rt] = max(sum[rt], lsum[rt]); sum[rt] = max(rsum[rt], sum[rt]); } void build(int l, int r, int rt) { if (l == r){ lsum[rt] = rsum[rt] = sum[rt] = 1; scanf("%d", &a[l]); return; } int mid = (l + r) >> 1; build(lson); build(rson); up(l, r, rt); } int ask(int L, int R, int l, int r, int rt) { if (L <= l&&r <= R) return sum[rt]; int ans1 = -1; int ans2 = -1; int ans = -1; int mid = (l + r) >> 1; if (L <= mid) ans1 = ask(L, R, lson); if (R > mid) ans2 = ask(L, R, rson); if (a[mid] == a[mid + 1]) ans = min(rsum[rt << 1], mid - L + 1) + min(lsum[rt << 1 | 1], R - mid); ans = max(ans, ans1); ans = max(ans, ans2); return ans; } int main() { int n, q, l, r; while (cin >> n, n){ cin >> q; build(1, n, 1); for (int i = 0; i < q; i++){ scanf("%d%d", &l, &r); printf("%d ", ask(l, r, 1, n, 1)); } } return 0; }