题目大意

给定长度为 \(n\) 的不减数组 $a_1, a_2, ... ,a_n \(，\)q$次询问区间 \([i,j]\) 内出现最多的数字次数 $ n,q < 1e5 $。

解题思路

典型的线段树问题。与简单RMQ只需要保存区间最大值最小值不同，这里我们利用数组单调性质，每个节点保存最大次数\(num\)，区间左端点数值次数\(ln\) 和右端点数值出现次数 \(rn\)。

查询区间 \([a,b]\) 时有如下性质，分别查询左右子区间，然后再考虑 \(data[mid]=data[mid+1]\), 则分布在左右子区间两段间的次数为 左子节点的\(rn\) 与右子节点的\(ln\)和， 取三者最大值即可。

建立线段树时需要注意正确计算 \(num, ln, rn\)，具体见代码。

算法实现

#include 
    
     #include 
     
      using namespace std;int data[100005];struct T{    int ln, rn;    int num;}node[300005];void build(int k, int a, int b)  // node[k] -> [a,b]{    if (a == b) {        node[k].ln = node[k].rn = node[k].num = 1;        return;    }    int left = 2 * k + 1, right = 2 * k + 2;    int mid = (a + b) / 2;    build(left, a, mid);    build(right, mid + 1, b);    T &p = node[k];    T &pl = node[left], &pr = node[right];    if (data[b] == data[mid]) {        p.rn = pr.rn + pl.rn;    }    else {        p.rn = pr.rn;    }    if (data[a] == data[mid + 1]) {        p.ln = pl.ln + pr.ln;    }    else {        p.ln = pl.ln;    }    p.num = max(pl.num, pr.num);    p.num = max(p.ln, p.num);    p.num = max(p.rn, p.num);    if (data[mid] == data[mid + 1])        p.num = max(p.num, pl.rn + pr.ln);    return;}int query(int k, int a, int b, int qa, int qb){    if (qa <= a && qb >= b) {        return node[k].num;    }    if (qa > b || qb < a)        return 0;    int left = 2 * k + 1, right = 2 * k + 2;    int mid = (a + b) / 2;    if (qa > mid)        return query(right, mid + 1, b, qa, qb);    else if (qb <= mid)        return query(left, a, mid, qa, qb);    int al = query(left, a, mid, qa, qb);    int ar = query(right, mid + 1, b, qa, qb);    int ans = max(al, ar);    T &p = node[k];    T &pl = node[left], &pr = node[right];    if (data[mid] == data[mid + 1]) {        int t = min(pl.rn, mid+1-qa) + min(pr.ln, qb-mid);        ans = max(ans, t);    }    return ans;}int main(){    int n, q;    while (true) {        scanf("%d", &n);        if (n == 0)            break;        scanf("%d", &q);        for (int i = 1; i <= n; i++)            scanf("%d", data + i);        build(0, 1, n);        int qa, qb;        while (q--) {            scanf("%d %d", &qa, &qb);            printf("%d\n", query(0, 1, n, qa, qb));        }    }    return 0;}