题目描述
题目链接←戳我
给出一个非递减数列，多次查询，每次查询一个区间内 出现次数最多的数 的出现次数（中文小心被绕进去，原题的英文还是很好理解的）
题目分析
应用分块的思想，把数字相同的分为一块，cnt[i]表示第i块中数字的个数，L[i]表示第i块的下标左边界，R[i]表示第i块的下标右边界(均为闭区间)，bel[i]表示第i个数字属于第几块，使用ST表预处理区间cnt的最大值
-1 -1 1 1 1 1 3 10 10 10
cnt[times] 2 4 1 3
L[i] 1 3 7 8
R[i] 2 6 7 10
则区间[l,r]的答案为
R[bel[l]]-l+1
r-L[bel[r]]+1
第bel[l]+1块到bel[r]-1块的cnt[i]的最大值
这三者中的最大值
代码参考 /* * @Author: CHAOS_ORDER * @Date: 2019-09-14 14:58:21 * @LastEditors: CHAOS_ORDER * @LastEditTime: 2019-09-17 16:43:21 * @Description: C - Frequent values http://acm.hdu.edu.cn/showproblem.php?pid=1806 * @Status: Accepted 280ms */#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <iomanip>#include <cstdio>#include <string>#include <vector>#include <cmath>#include <deque>#include <queue>#include <stack>#include <map>#include <set>using namespace std;#define pdn(i) printf("%dn", i)#define plldn(i) printf("%lldn", i)#define pchstrn(i) printf("%sn", i)#define sdd(i, j) scanf("%d%d", &i, &j)#define slldd(i, j) scanf("%lld%lld", &i, &j)#define sdt(i, j, k) scanf("%d%d%d", &i, &j, &k)#define slldt(i, j, k) scanf("%lld%lld%lld", &i, &j, &k)#define sd(i) scanf("%d", &i)#define pd(i) printf("%d", i)#define slld(i) scanf("%lld", &i)#define plld(i) printf("%lld", i)#define schstr(i) scanf("%s", i)#define pchstr(i) printf("%s", i)#define For(i, begin, end) for (register int i = begin; i <= end; i = i + 1)#define rFor(i, begin, end) for (register int i = begin; i >= end; i = i - 1)#define newline printf("n")#define pause system("pause")#define mod 1000000007#define inf 0x3f3f3f3ftypedef long long ll;typedef unsigned long long ull;const ll maxn = 1e5 + 8;const ll maxm = 1e7 + 8;int a[maxn], st[maxn][20], bel[maxn], cnt[maxn], L[maxn], R[maxn];int times = 1;void st_pretreat(){ For(i, 1, times) st[i][0] = cnt[i]; for (int j = 1; (1 << j) <= times; j++) { for (int i = 1; i + (1 << j) - 1 <= times; i++) { st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } }}int query(int l, int r){ if (l > r) return 0; int len = log2(r - l + 1); return max(st[l][len], st[r - (1 << len) + 1][len]);}int main(){ int n, q; int l, r; while (sd(n), n) { sd(q); times = 1; For(i, 1, n) sd(a[i]); int sta = a[1]; L[times] = 1; for (int i = 1; i <= n; i++) { if (a[i] != sta) { R[times] = i - 1; cnt[++times]++; L[times] = i; sta = a[i]; bel[i] = times; } else { bel[i] = times; cnt[times]++; } } R[times] = n; st_pretreat(); while (q--) { sdd(l, r); if (bel[l] ^ bel[r]) printf("%dn", max(max(R[bel[l]] - l + 1, r - L[bel[r]] + 1), query(bel[l] + 1, bel[r] - 1))); else pdn(r - l + 1); } memset(cnt, 0, sizeof(cnt[0]) * n); } return 0;}