http://poj.org/problem?id=3368
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 24727 | Accepted: 8612 |
Description
You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
Sample Output
1 4 3
Source
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include<cstdio> #include<string> #include<cstring> #include <stdio.h> #include <string.h> #include <vector> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f using namespace std; const int N = 1e5 + 9 ; const int M = 1e5 + 9 ; int dp[N][40] , a[N] , b[N] ;//b数组统计连续相同个数 int n , q ; void RMQ() { for(int i = 1 ; i <= n ; i++) { dp[i][0] = b[i]; } for(int j = 1 ; j < 30 ; j++) { for(int i = 1 ; i <= n ; i++) { if(i + (1 << j) - 1 <= n) { dp[i][j] = max(dp[i][j-1] , dp[i+(1<<(j-1))][j-1]); } } } } int query(int l , int r) { if(r < l) return 0 ;//这个条件不能少，如果查询左右端点相等时，l将大于r int ans = 0 ; int k = (int)log2(r - l + 1); ans = max(dp[l][k] , dp[r - (1 << k) + 1][k]); return ans ; } int main() { while(~scanf("%d" , &n) && n) { scanf("%d" , &q); //init(); for(int i = 1 ; i <= n ; i++) { scanf("%d" , &a[i]); b[i] = 1 ; } for(int i = 2 ; i <= n ; i++) { if(a[i] == a[i-1]) { b[i] = b[i-1] + 1 ; } else { b[i] = 1 ; } } RMQ(); for(int i = 1 ; i <= q ; i++) { int l , r , ans = 0; scanf("%d%d" , &l , &r); int t = l ; while(t <= r && a[t] == a[t-1])//以防左端点被截断 { t++; } ans = max(t - l , query(t , r));//左端点被截断的话，需要用值减去下标 printf("%d\n" , ans); } } return 0 ; }
线段树
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <algorithm> #include <iostream> #include<cstdio> #include<string> #include<cstring> #include <stdio.h> #include <string.h> #include <vector> #define ME(x , y) memset(x , y , sizeof(x)) #define SF(n) scanf("%d" , &n) #define rep(i , n) for(int i = 0 ; i < n ; i ++) #define INF 0x3f3f3f3f using namespace std; const int N = 1e5 + 9 ; const int M = 1e5 + 9 ; int dp[N][40] , a[N] , b[N] ;//b数组统计连续相同个数 int n , q , k = 1 , ans = 0; struct node{ int l , r , val ; }tree[N << 2]; void build(int l , int r , int root) { tree[root].l = l , tree[root].r = r ; if(l == r) { tree[root].val = b[k++]; // cout << root << " " << tree[root].val << endl ; return ; } int mid = (l + r) >> 1; build(l , mid , root*2); build(mid+1 , r , root*2+1); tree[root].val = max(tree[root*2].val , tree[root*2+1].val); } void query(int l , int r , int root) { if(r < l) return ; if(tree[root].l >= l && tree[root].r <= r) { ans = max(tree[root].val , ans) ; return ; } int mid =(tree[root].l + tree[root].r) >> 1; if(l <= mid) query(l , r , root*2); if(r > mid) query(l , r , root*2+1); } int main() { while(~scanf("%d" , &n) && n) { scanf("%d" , &q); //init(); for(int i = 1 ; i <= n ; i++) { scanf("%d" , &a[i]); b[i] = 1 ; } for(int i = 2 ; i <= n ; i++) { if(a[i] == a[i-1]) { b[i] = b[i-1] + 1 ; } else { b[i] = 1 ; } } // memset(tree , 0 ,sizeof(tree)); k = 1 ; build(1 , n , 1); for(int i = 1 ; i <= q ; i++) { int l , r , sum = 0; scanf("%d%d" , &l , &r); int t = l ; while(t <= r && a[t] == a[t-1])//以防左端点被截断 { t++; } query(t , r , 1); sum = max(ans , t - l); printf("%d\n" , sum); ans = 0 ; } } return 0 ; }
原文：https://www.cnblogs.com/nonames/p/11332598.html