连续相同的数为一段 cnt[i] 为第i段出现次数
对于每次询问l,r
判断l,r,分别属于哪一段 比如说是 x,y 那么求x+1 到y-1段的RMQ
另外x,y分别还有一部分 别忘记
RMQ 线段树都可以解
RMQ
#include <cstdio> #include <cstring> #include <map> #include <algorithm> using namespace std; const int maxn = 100010; int a[maxn];//输入的数 连续相同的分成一段 int value[maxn];//每一段的值 int cnt[maxn];//每一段的个数 int num[maxn];//每个数所在哪一段 int l[maxn];//每个数在段的左界限 int r[maxn];//每个数在段数右界限 int dp[maxn][50]; void RMQ_init(int n) { for(int i = 1; i <= n; i++) dp[i][0] = cnt[i]; for(int j = 1; (1<<j) <= n; j++) { for(int i = 1; i + (1<<j) - 1 <= n; i++) { dp[i][j] = max(dp[i][j-1], dp[i + (1 << (j-1))][j-1]); } } } int RMQ(int l, int r) { int k = 0; while(1 << (k+1) <= r - l + 1) k++; return max(dp[l][k], dp[r-(1<<k)+1][k]); } int main() { int n, m; int i, j; while(scanf("%d", &n) && n) { scanf("%d", &m); map <int, int> mp; map <int, int> ::iterator it; for(i = 1; i <= n; i++) { scanf("%d", &a[i]); mp[a[i]]++; } int sum = 0; for(it = mp.begin(), i = 1, j = 1; it != mp.end(); it++, i++) { sum += it -> second; while(j <= sum) { l[j] = sum - it -> second + 1; r[j] = sum; num[j] = i; j++; } value[i] = it -> first; cnt[i] = it -> second; } //n = i; int len = i - 1; //for(i = 1; i <= n; i++) // printf("%d %d %d\n",num[i], l[i], r[i]); //for(i = 1; i <= len; i++) // printf("%d %d\n",value[i], cnt[i]); RMQ_init(len); while(m--) { int x, y; scanf("%d %d", &x, &y); if(num[x] == num[y]) printf("%d\n", y-x+1); else { int s1 = r[x] - x + 1; int s2 = y - l[y] + 1; s1 = max(s1, s2); int s3 = 0; if(num[y] - 1 >= num[x] + 1) s3 = RMQ(num[x]+1, num[y]-1); printf("%d\n",max(s1, s3)); } } } return 0; }