PKU 3368(線分ツリー+離散化)
Frequent values
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 5869
Accepted: 2062
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
Sample Output
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 5869
Accepted: 2062
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
0Sample Output
1
4
3//ai ≤ ai+1 ，
#include <iostream>
using namespace std;
#define N 100010
#define max(a,b) (a>b?a:b)
struct LineTree
{
int l,r,len,mid;
int a,b,MAX; //a b MAX
}tree[N*3];
int res[N];
int len;
int val[N];
void Build(int root,int a,int b)
{
tree[root].l = a;
tree[root].r = b;
tree[root].mid = (a+b)>>1;
tree[root].len = b-a;
tree[root].a = res[a];
tree[root].b = res[b];
if(tree[root].len == 1)
{
tree[root].MAX = res[b] - res[a];
return;
}
Build(root<<1,a,tree[root].mid);
Build((root<<1)+1,tree[root].mid,b);
tree[root].MAX = max(tree[root<<1].MAX , tree[(root<<1)+1].MAX);
}
int Search(int root,int a,int b)
{
if(tree[root].a == a && tree[root].b == b)
{
return tree[root].MAX;
}
if(tree[root].len == 1) return b-a;
if(b <= tree[root<<1].b) return Search(root<<1,a,b);
else if(tree[(root<<1)+1].a <= a) return Search((root<<1)+1,a,b);
else
{
return max(Search(root<<1,a,tree[root<<1].b),Search((root<<1)+1,tree[(root<<1)+1].a,b));
}
}
int main()
{
int n,m,i,a,b;
while (scanf("%d",&n),n)
{
scanf("%d",&m);
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
len=2;
res[1] = 1;
for(i=2;i<=n;i++)
{
if(val[i] != val[i-1])
res[len++] = i;
}
res[len] = n+1;
Build(1,1,len);
while (m--)
{
scanf("%d%d",&a,&b);
printf("%d/n",Search(1,a,b+1));
}
}
return 0;
}