POJ - 3368 Frequent values
UVA - 11235 Frequent values
題目
題目給出一個長度為 n 非遞減序列,q 次詢問區間最長連續相等序列長度。
分析
區間問題,線段樹肯定可以做,不過應該有點麻煩。可以看出題目是離線詢問,沒有更新部分,隻要處理一次序列即可。
因為給出序列為非遞減序列,也就是可以分成一段一段的,即遊程編碼,例如:
-1,1,1,2,2,2,4,
編碼為:
(-1, 1), (1, 2), (2, 3), (4, 1)
這樣問題就變為在所給區間完整包含的段裡面取最大值,兩邊的段分别考慮。圖示:
中間的就是ST表找最值,兩邊的直接比長度即可。
代碼
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define d(x) cout<<(x)<<endl;
const int N = 1e5 + 10;
int n, q;
int a[N], st[N][20];
int val[N], cnt[N]; // 每段的值,每段的長度
int id[N], l[N], r[N]; // i 所在段的編号,左端點,右端點
void rmq(){
for (int i = 1; i <= n; i++){
st[i][0] = cnt[i];
}
for (int j = 1; (1 << j) <= n; j++){
for (int i = 1; i + (1 << j) - 1 <= n; i++){
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int solve(int x, int y){
if(id[x] == id[y]){
return y - x + 1;
}
int ans = max(r[x] - x + 1, y - l[y] + 1);
int L = id[x] + 1, R = id[y] - 1;
if(L <= R){
int k = log2(R - L + 1);
ans = max(ans, max(st[L][k], st[R - (1 << k) + 1][k]));
}
return ans;
}
int main()
{
while(scanf("%d", &n)){
if(!n)
break;
scanf("%d", &q);
int k = 1, x, y; // 段數
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
a[n + 1] = a[n] + 1; // 處理最後一段
int start = 0;
for (int i = 1; i <= n + 1; i++){
if(i == 1 || a[i] > a[i-1]){
if(i > 1){
cnt[k++] = i - start;
for (int j = start; j < i; j++){
id[j] = k - 1;
l[j] = start;
r[j] = i - 1;
}
}
start = i;
}
}
rmq();
while(q--){
scanf("%d%d", &x, &y);
printf("%d\n", solve(x, y));
}
}
return 0;
}