UVA 11235 Frequent values (RMQ)
題意：給一個非降序排列的整數數組a，你的任務是對於一系列詢問(i, j)，回答ai,ai+1...aj中次數出現最多的值所出現的次數。
思路：由於數列是非降序的，所以所有相等的數都會聚集在一起。這樣我們就可以把整個數組進行編碼。如-1,1,1,2,2,2,4就可以編碼成(-1,1),(1,2),(2,3),(4,1)表示（a，b）數組中的a連續出現了b次。用num[i]表示原數組下表是i的數在編碼後的第num[i]段。left[i],right[i]表示第i段的左邊界和右邊界，用coun[i]表示第i段有conu[i]個相同的數。這樣的話每次查詢(L, R)就只要計算(right[L]-L+1),(R-left[R]+1)和RMQ(num[L]+1, num[R]-1)這三個值的最大值就可以了。
其中，RMQ是對coun數組進行取件查詢的結果。
特殊的，如果L和R在同一個區間內的話，那麼結果就是（R-L+1）
AC代碼：
#include
#include
#include
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MAXM = 100005;
const double eps = 1e-12;
int num[MAXN], coun[MAXN], Left[MAXN], Right[MAXN];
int n, q, a, last, tot;
int DP[MAXN][20];
void init_RMQ()
{
memset(DP,0,sizeof(DP));
for(int i=1;i<=tot;i++) DP[i][0] = coun[i];
for(int j=1;(1< R) return 0;
int k = 0;
while((1<<(1+k)) <= R-L+1) k++;
return max(DP[L][k], DP[R-(1<
