本文主要是介绍uva 11235，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数据结构 RMQ算法 左右左右 写得有点晕了 。。。。。
/*************************************************************************> Author: xlc2845 > Mail: xlc2845@gmail.com> Created Time: 2013年11月07日 星期四 11时05分22秒************************************************************************/#include <cstdio>
//#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long
#define maxn 100010
using namespace std;int val[maxn], cou[maxn], n, q, num[maxn], left[maxn], right[maxn], d[maxn][100];
void init()
{memset(val, 0, sizeof(val));memset(cou, 0, sizeof(cou));memset(d, 0, sizeof(d));
}
void init_RMQ(int k)
{for(int i = 0; i < k; i++)d[i][0] = cou[i];for(int j = 1; (1 << j) <= n; j++)for(int i = 0; i+(1 << j) - 1 < n; i++)d[i][j] = max(d[i][j-1], d[i+(1 << (j-1))][j-1]);
}
int RMQ(int L, int R)
{if(L > R)return 0;int k = 0;while((1 << (k+1)) <= R-L+1) k++;return max(d[L][k], d[R-(1 << k)+1][k]);
}
int main()
{while(scanf("%d", &n) == 1 && n){init();scanf("%d",&q);int j = 1, x;scanf("%d", &x);left[j] = 1;num[1] = j;val[1] = x;cou[1] = 1;for(int i = 2; i <= n; i++){scanf("%d", &x);if(x == val[j]){num[i] = j;cou[j]++;}else{right[j] = i-1;j++;val[j] = x;num[i] = j;cou[j] ++;left[j] = i;}}right[j] = n;init_RMQ(j);while(q--){int rr,ll;scanf("%d%d", &ll, &rr);int R = num[rr], L = num[ll];if(R == L) printf("%d\n", rr-ll+1);else{int ans = right[L]-ll+1;ans = max(rr-left[R]+1, ans);ans = max(ans, RMQ(L+1, R-1));printf("%d\n",ans);}}}return 0;
}
这篇关于uva 11235的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
