|
Frequent values
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 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 |
题意：一个具有n(1~100000)个点的序列，从大到小排序，有一些点的大小是相等的，问区间[a,b]上，相等大小的点最多是几个。
思路：线段树+离散化。离散的运用：将连续的相等的一个区间的点集，聚集为线段树的一个节点，并且在这个节点上有信息能体现出这个区间的性质。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=100010; #define L(rt) (rt<<1) #define R(rt) (rt<<1|1) struct Tree{ int l,r; int len; // len保存这个点集的点的数量 }tree[N<<2]; struct Point{ int x,y; }seg[N]; int num[N],hash[N]; void PushUp(int rt){ tree[rt].len=max(tree[L(rt)].len,tree[R(rt)].len); } void build(int l,int r,int rt){ tree[rt].l=l; tree[rt].r=r; if(l==r){ tree[rt].len=seg[l].y-seg[l].x+1; return; } int mid=(l+r)>>1; build(l,mid,L(rt)); build(mid+1,r,R(rt)); PushUp(rt); } int ans; void query(int L,int R,int rt){ if(tree[rt].l==L && tree[rt].r==R){ ans=max(ans,tree[rt].len); return ; } int mid=(tree[rt].l+tree[rt].r)>>1; if(R<=mid) query(L,R,L(rt)); else if(L>=mid+1) query(L,R,R(rt)); else{ query(L,mid,L(rt)); query(mid+1,R,R(rt)); } } int main(){ //freopen("input.txt","r",stdin); int n,m; while(~scanf("%d",&n) && n){ scanf("%d",&m); for(int i=1;i<=n;i++) scanf("%d",&num[i]); int cnt=0,pre=999999; for(int i=1;i<=n;i++){ // 离散化，将点的序列离散化为一个个的点集 if(num[i]!=pre){ pre=num[i]; cnt++; seg[cnt].x=i; seg[cnt].y=i; }else seg[cnt].y=i; hash[i]=cnt; // hash保存序列上第i个点，对应的点集的下标 } build(1,cnt,1); int a,b; while(m--){ scanf("%d%d",&a,&b); int loc1=hash[a]; //如下，好的主函数操作能很大程度上简化线段树的复杂度 int loc2=hash[b]; if(loc1==loc2) // 情况1：[a,b]为一个点集 printf("%d\n",b-a+1); else{ // 情况2，3：[a,b]包含多个点集 int n1=seg[loc1].y-a+1; int n2=0; int n3=b-seg[loc2].x+1; if(loc2-loc1>1){ //情况3：[a,b]包含3个以上点集，中间点集最大值用到线段树 ans=0; query(loc1+1,loc2-1,1); n2=ans; } printf("%d\n",max(n1,max(n2,n3))); } } } return 0; }