UVA11235 频繁出现的数值 ——RMQ

蓝书p198

题意：

给出一个非降序排列的整数数组，回答一系列询问，找出[l, r]中出现次数最多的值所出现的次数。

注意第52、55行对边界的处理

由于数组从下标为0开始存储的，所以最后回答询问的时候l--,r--

// Decline is inevitable,
// Romance will last forever.
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
//#define mp make_pair
#define pii pair
#define fi first
#define se second
#define ll long long
//#define int long long
const int maxn = 1e5 + 10;
const int maxm = 25;
const int P = 1e9 + 7;
int n, q;
struct RMQ {
    int d[maxn][30];
    void init(const vector& A) {
        int n = (int)A.size();
        for(int i = 0; i < n; i++) d[i][0] = A[i];
        for(int j = 1; (1 << j) <= n; j++)
            for(int i = 0; i+(1<> n && n) {
        cin >> q;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        a[n] = a[n-1] + 1;  //
        vector count;
        int start = -1;
        for(int i = 0; i <= n; i++) {       //
            if(i == 0 || a[i] != a[i-1]) {
                if(i > 0) {
                    count.push_back(i-start);
                    for(int j = start; j < i; j++) {
                        num[j] = (int)count.size() - 1;
                        le[j] = start;
                        ri[j] = i-1;
                    }
                }
                start = i;
            }
        }
        rmq.init(count);
        while(q--) {
            int l, r;
            cin >> l >> r;
            l-- ; r--;  //
            int ans = 0;
            if(num[l] == num[r]) ans = r - l + 1;
            else {
                ans = max(ri[l]-l, r-le[r]) + 1;
                if(num[l]+1

UVA11235 频繁出现的数值 ——RMQ

C/C++/C#相关栏目本月热门文章