题目描述
给定一个序列，多次询问一段区间 [l,r]，求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const double eps = 1e-8;
const ll lnf = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 200100;
const int mod = 1e9 + 7;
int a[maxn], b[maxn], ans[maxn], pos[maxn], res = 0;
int mi[maxn], ma[maxn], st[maxn];
struct node
{
    int l, r, id;
}q[maxn];

bool cmp(const node& a, const node& b)
{
    if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
    else  return a.r < b.r;
}

int get(int l, int r)
{
    int ans = 0, cnt = 0;
    for (int i = l;i <= r;i++)
    {
        if (!mi[a[i]]) mi[a[i]] = i, st[++cnt] = a[i];
        else ans = max(ans, i - mi[a[i]]);
    }
    while (cnt)
        mi[st[cnt--]] = 0;
    return ans;
}

int main(void)
{
    int n, m;
    scanf("%d", &n);
    for (int i = 1;i <= n;i++)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    int pc = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1;i <= n;i++)
        a[i] = lower_bound(b + 1, b + pc + 1, a[i]) - b;

    scanf("%d", &m);
    int t = sqrt(m);
    for (int i = 1;i <= n;i++)
        pos[i] = (i - 1) / t + 1;
    for (int i = 1;i <= m;i++)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;

    sort(q + 1, q + m + 1, cmp);

    int len = pos[n];
    for (int i = 1, j = 1;j <= len;j++)
    {
        int askr = min(j * t, n) + 1, ql = askr, qr = ql - 1;
        int res = 0, cnt = 0;
        for (;pos[q[i].l] == j;i++)
        {
            if (pos[q[i].r] == j)
            {
                ans[q[i].id] = get(q[i].l, q[i].r);
                continue;
            }
            while (qr < q[i].r)
            {
                ++qr;
                ma[a[qr]] = qr;
                if (!mi[a[qr]]) mi[a[qr]] = qr, st[++cnt] = a[qr];
                res = max(res, qr - mi[a[qr]]);
            }
            int now = res;
            while (ql > q[i].l)
            {
                --ql;
                if (!ma[a[ql]]) ma[a[ql]] = ql;
                res = max(res, ma[a[ql]] - ql);
            }
            ans[q[i].id] = res;
   
            while (ql <= askr)
            {
                if (ma[a[ql]] == ql) ma[a[ql]] = 0;
                ql++;
            }
            res = now;
        }
        while (cnt)
            ma[st[cnt]] = mi[st[cnt]] = 0, cnt--;
    }
    for (int i = 1;i <= m;i++)
        printf("%d\n", ans[i]);
    return 0;
}