Frequent values
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 13352 |
|
Accepted: 4913 |
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 Ulm Local 2007 |
[Submit] [Go Back] [Status] [Discuss]
这个题绝对是原创！！！
哎~提起这个题真的好苦逼，是比赛的一个题，比赛时真的感觉是对的，但是时间不够，还是没有做出来，结束后
做了好久还是无果，看题解感觉和别人的一样的思路啊，最后决定独立自主，自力更生，终于做出来了，%>_<%，
bug了好久，在这里，我就留下我bug的痕迹吧，方便日后看
题意：n个数，m次询问，每一次 a b,输出出现最多次数的数的次数，不过题目说序列为不递减序列，所以相同的数为邻居
思路：线段树，因为时间很紧，具体程序运行过程我注释在程序中
#include
#include
#include
#include
#define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) using namespace std; #define N 100005 struct stud{ int le,ri; //区间左,右端点 int lle,rri; //区间左值，右值 int ls,rs,ms;//区间跟左值（右值）相同的数的个数 }f[N*4]; //如果不懂，后面有提试 int a[N]; void pushup(int pos) { f[pos].lle=f[L(pos)].lle; f[pos].rri=f[R(pos)].rri; f[pos].ls=f[L(pos)].ls; f[pos].rs=f[R(pos)].rs; f[pos].ms=max(f[L(pos)].ms,f[R(pos)].ms); if(f[L(pos)].rri==f[R(pos)].lle) { if(f[L(pos)].ls==f[L(pos)].ri-f[L(pos)].le+1) f[pos].ls+=f[R(pos)].ls; if(f[R(pos)].rs==f[R(pos)].ri-f[R(pos)].le+1) f[pos].rs+=f[L(pos)].rs; int temp=f[L(pos)].rs+f[R(pos)].ls; f[pos].ms=max(f[pos].ms,temp); } } void build(int pos,int le,int ri) { f[pos].le=le; f[pos].ri=ri; if(le==ri) { f[pos].lle=f[pos].rri=a[le]; f[pos].ls=f[pos].rs=f[pos].ms=1; return ; } int mid=MID(le,ri); build(L(pos),le,mid); build(R(pos),mid+1,ri); pushup(pos); //想想什么是递归， //当前面的build执行完了再执行这一步（记住上一步build中也有 pushup） //自己模拟过程 } int query(int pos,int le,int ri) { if(f[pos].le>=le&&f[pos].ri<=ri) { // printf("le=%d ri=%d temp=%d\n",le,ri,f[pos].ms); return f[pos].ms; } int mid=MID(f[pos].le,f[pos].ri); if(mid>=ri) return query(L(pos),le,ri); else if(mid