UVA - 11235 —— Frequent values 【RMQ】
7617 ワード
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23846
問題:
1.トリップ符号化(シーケンスを(value,num)のセグメントのキー値ペア形式に変換)後、問題をほぼRMQ問題に変換し、いくつかの詳細だけを単独で考慮する
2.クエリの2つの下付きlが、rが同じキー値ペアに属する場合、答えは(r-l+1)である.そうでない場合、答えは3つ(または2つ)の値の最大値です.詳細はコードを参照してください.
転載先:https://www.cnblogs.com/AcIsFun/p/5456951.html
問題:
1.トリップ符号化(シーケンスを(value,num)のセグメントのキー値ペア形式に変換)後、問題をほぼRMQ問題に変換し、いくつかの詳細だけを単独で考慮する
2.クエリの2つの下付きlが、rが同じキー値ペアに属する場合、答えは(r-l+1)である.そうでない場合、答えは3つ(または2つ)の値の最大値です.詳細はコードを参照してください.
#include
#include
#include
#include <string>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 100000 + 5, MAXK = 17 + 5;
int d[MAXN][MAXK];
int val[MAXN], num[MAXN];
int id[MAXN], L[MAXN], R[MAXN];
int size;
void build(int n)
{
for(int i=1; i<=n; i++) {
d[i][0] = num[i];
}
for(int j=1; (1<) {
for(int i=1; i + (1 << j) - 1 <= n; i++) {
d[i][j] = max(d[i][j-1], d[i+(1<1))][j-1]);
}
}
}
int query(int l, int r)
{
if(l>r) return -INF; // , , !
int w = r - l + 1;
int x = 0;
while((1<1) <= w) x++;
return max(d[l][x], d[r-(1<1][x]);
}
int main ()
{
int n, q, l, r;
while(scanf("%d", &n) != EOF && n) {
scanf("%d", &q);
size = 1;
int pre, x;
for(int i=1; i<=n; i++) {
scanf("%d", &x);
if(i==1) {
val[size] = x;
num[size] = 1;
id[i] = size;
L[size] = i;
} else if(x != pre) {
R[size] = i-1;
size++;
val[size] = x;
num[size] = 1;
id[i] = size;
L[size] = i;
} else {
num[size]++;
id[i] = size;
}
pre = x;
}
R[size] = n;
build(size);
while(q--) {
scanf("%d%d", &l, &r);
int maxn;
if(id[l] == id[r]) {
maxn = r - l + 1;
} else {
maxn = R[id[l]] - l + 1;
maxn = max(maxn, r - L[id[r]] + 1);
maxn = max(maxn, query(id[l]+1, id[r]-1));
}
printf("%d
", maxn);
}
}
return 0;
}
転載先:https://www.cnblogs.com/AcIsFun/p/5456951.html