连续相同的数为一段 cnt[i] 为第i段出现次数
对于每次询问l,r
判断l,r,分别属于哪一段 比如说是 x,y 那么求x+1 到y-1段的RMQ
另外x,y分别还有一部分 别忘记
RMQ 线段树都可以解
RMQ
#include #include #include #include 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< mp; map ::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; }