最频繁值（区间最值POJ3368）

题目：
给定n个整数不下降序列。此外，还提供了几个由索引组成的查询。i和j (1≤i≤j≤n)。对于每个查询，确定整数中最频繁的值。

输入：
输入由几个测试用例组成。每个测试用例从包含两个整数的一行开始。n和q (1≤n，q≤100000)。下一行包含n整数a1，… an (-100000≤ai≤100000，每个i∈{1，…，n})由空格隔开的。以下内容q行每个包含一个查询，由两个整数组成。i和j (1≤i≤j≤n)表示查询的边界索引。在最后一个测试用例包含一个包含单个0的行。

输出：
对于每个查询，用一个整数打印一行：在给定范围内出现最频繁的值的次数。

样例输入：
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
样例输出：
1
4
3

题解：本题给定区间查最值，将各个区间的元素的出现次数累计，累计区间
F[i][j]表示[i，i+2^j -1]区间最大值，区间长度为2^j 。

（1）为了提高效率求出数据范围内的log值，将其存储在数组lb[]中。
整数log值得规律如下：
2^j 和它前一个数&运算必然为0，此时其log值比前一个数增加1。
例如：8的二进制1000,7的二进制0111，两者与运算为0，log（8）比log（7）增加1
除2ⁱ 外，其他数和前一个数的与运算不为0，其log值和前一个数相等。
首先 log[0]=-1
1&0=0: log[1]=log[0]+1=0
2&1=0: log[2]=log[1]+1=1
3&2=2: log[3]=log[2]=1
4&3=0: log[4]=log[3]+1=2
…

（2）将输入样例中元素的出现次数累计并存入F[i][0]中。

（3）创建ST。
（4）编写查询函数RMQ（int l,int r）

#include
#define maxn 1001
int lb[maxn];
int F[maxn][maxn];
int a[maxn];
using namespace std;
int n,q,l,r;
void Initlog()
{
	lb[0]=-1;
	for(int i=1;i<maxn;i++)
		lb[i]=(i&(i-1))?lb[i-1]:lb[i-1]+1;
}
void ST_cteate() {
	for(int j=1;j<=lb[n];j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r)
{
	if(l>r) return 0;
	int k=lb[r-l+1];
	return max(F[l][k],F[r-(1<<k)+1][k]);
}
int main()
{
	
	cin>>n>>q;
	for(int i=1;i<=n;i++) F[i][0]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		for(int j=1;j<i;j++)
			if(a[i]==a[j]) F[i][0]=max(F[i][0],F[j][0]+1);
			/*和最长上升子序列一样，每新拿一个数，都
			要和以前的所有数比较是否相等，如果相等取最大值加1 */
	} 
	Initlog();
	ST_cteate();
	for(int j=1;j<=q;j++) 
	{
		scanf("%d%d",&l,&r);
		int t=l;
		while(t<=r&&a[t]==a[t-1]) t++;//数据非递减有序，因此可以这样做
		cout<<max(t-l,RMQ(t,r))<<endl ;//t-l为第1个数在查询区间[l,r]的重复次数 
		
	}

	
}
/*
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57