uva 11235 Frequent values（游程編碼+區間最小值查詢）

uva 11235 Frequent values（游程編碼+區間最小值查詢）

游程編碼的基本原理是：用一個符號值或串長代替具有相同值的連續符號（連續符號構成了一段連續的“行程”。游程編碼因此而得名），使符號長度少於原始數據的長度。只在各行或者各列數據的代碼發生變化時，一次記錄該代碼及相同代碼重復的個數，從而實現數據的壓縮。

游程編碼（Run Length Encoding , RLE）

例如：5555557777733322221111111
游程編碼為：（5，6）（7，5）（3，3）（2，4）（1，7）

解題思路很好：

用value[i] count[i] 分別表示 第i段的數值 和 出現次數；

num[p] left[p] right[p]分別表示位置p所在段的編號和左右端點的位置。

每次查詢(left,right)的結果為以下三個部分的最大值：從left到left所在段結束處的元素個數、從right所在段開始到right處的元素個數、中間第num[left]+1段到第num[right]-1段的count的最大值。

特殊情況：如果left和right在同一段中，答案是R-L+1。

解決方法如下：

#include 
#include 
#include 
using namespace std;
const int maxn = 100001;

int n,q;
int d[maxn][35];
int a[maxn];
int value[maxn],count_[maxn];
int num[maxn],left[maxn],right[maxn];

void RMQ_int(){
    for(int i=0;i num[right_]-1) ans=max(ans,0);
                else{
                    ans=max(ans,RMQ(num[left_]+1,num[right_]-1));
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}