Frequent values
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1459 Accepted Submission(s): 535
Problem 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.
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
Hint
A naive algorithm may not run in time!
题意:
查找区间中出现频率最高的,并输出出现次数。
思路:
开始想了很久不知道怎么用到RMQ的,总感觉和最值没什么关系,后来发现对连续的数编号然后求出最大值就好了。
只是需要判断一下不是从1开始的,所以用的二分查找。
但是强行被二分Gank一波。总感觉二分用的不怎么熟练,好久去研究一下。就因为设置的方向不一样,写起来特别麻烦,导致后来还是要重写。
假设我想取一个最接近左边的值,所以设定的l = mid,但是就会导致2和3的时候卡死。后来换了下方向就行了
当你取到3的时候,下一次还是会往下跳,- -!基础真的糟
/* */ #include <functional> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <Map> using namespace std; typedef long long ll; typedef long double ld; using namespace std; const int maxn = 100010; int dp[maxn][20]; int m[maxn]; int a[maxn]; int b[maxn]; void iniRMQ(int n,int c[]) { m[0] = -1; for(int i = 1; i <= n; i++) { m[i] = ((i&(i-1)) == 0)? m[i-1]+1:m[i-1]; dp[i][0] = c[i]; } for(int j = 1; j <= m[n]; j++) { for(int i = 1; i+(1<<j)-1 <= n; i++) dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } } int RMQ(int x,int y) { int k = m[y-x+1]; return max(dp[x][k],dp[y-(1<<k)+1][k]); } int get_bi(int s,int t) { int l =s,r = t; int to = a[t]; while(l < r) { int mid = ((l+r)>>1); if(a[mid] >= to) r = mid; else l = mid+1; } return r; } int main() { int n,m,T; while(scanf("%d",&n) != EOF && n) { scanf("%d",&m); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } int t; for(int i = n; i >= 1; i--) { if(i == n) t = 1; else { if(a[i] == a[i+1])t++; else t=1; } b[i] = t; } // for(int i = 1;i <= n;i++) // printf("%d ",b[i]); iniRMQ(n,b); while(m--) { int s,t,ans; scanf("%d%d",&s,&t); int tl = get_bi(s,t); // printf("%d ",tl); ans = t- tl+1; if(tl-1 > s) ans = max(ans,RMQ(s,tl-1)); printf("%d ",ans); } } return 0; }