这道题是rmq，再加上一个解决溢出。

刚开始我也想过用rmq，虽然不知道它叫什么，但是我知道应该这样做。可是后来没想到这道题的特殊性，也就是解决溢出的方法，就放弃了。

rmq可以用线段树，也可以用dp。  这道题都可以过的，而且线段树要快一些。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define max(a,b) (a > b ? a : b)const int maxm = 2000010;const int maxn = 200010;int v[maxm], n, m;int data[maxn];int pre[maxn], len[maxn], lg[maxn];int rmq[maxn][25];void rmq_init(){    for(int i = 0; i <= lg[n]; i++)        for(int j = 0; j + (1 << i) - 1 < n; j++)        {            if(i == 0)                rmq[j][i] = len[j];            else                rmq[j][i] = max(rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1]);        }}int rmq_max(int l, int r){    if(r < l)        return 0;    int t = r - l + 1;    return max(rmq[l][lg[t]], rmq[r - (1 << (lg[t])) + 1][lg[t]]);}int main(){    lg[0] = -1;     for(int i = 1; i < maxn; i++)        lg[i]=lg[i >> 1]+1;    while(cin >> n)    {        cin >> m;        for(int i = 0; i < n; i++)            scanf("%d", &data[i]);        memset(v, -1, sizeof(v));        int p1 = 0;        int p2 = 0;        while(p2 < n)        {            if(v[data[p2] + 1000000] >= p1)            {                for(int i = p1; i <= v[data[p2] + 1000000]; i++)                {                    len[i] = p2 - i;                    pre[i] = p2 - 1;                }                p1 = v[1000000 + data[p2]] + 1;            }            v[1000000 + data[p2]] = p2;            p2++;        }        for(int i = p1; i < n; i++)        {            len[i] = n - i;            pre[i] = n - 1;        }        /*for(int i = 0; i < n; i++)        cout << pre[i]  << " "  ;        cout << endl;*/        int l, r, ans;        rmq_init();        for(int i = 0; i < m; i++)        {            scanf("%d%d", &l, &r);            int t = lower_bound(pre + l, pre + r, r) - pre;            //cout << endl << t << endl;            ans = r - t + 1;            //cout << ans << endl << endl;            r -= ans;            //cout << r << endl;            ans = max(ans, rmq_max(l, r));           printf("%d\n",ans);        }    }}