题目：点击此处

题意：给你n个数，q个询问，问每个区间的数最少需要几步可以删除完

删除的是一个等差序列

由于第一次删除之后，剩下的数字随机排列，所以，只要第一次删除可以把一种数字全部删除，剩下的步数就是数字种类数

总步数即为  总的种类数

 如果一次删不完一种数，那么答案就是总的种类数+1

判断是否是等差序列需要预处理  两个数组  fl[N],fr[N];

fl[i]表示i位置往左第一个构不成等差序列的位置

fr[i]同理；

 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
const int N=100005; 
struct node
{
    int x,y,p;
}q[N];
bool cmp(node a,node b)
{
    if (a.x/block!=b.x/block) 
        return  a.x/block<b.x/block;
    return a.y<b.y;
}
int aa[N];
int bak[N];
int pre[N];
int last[N];
int fl[N],fr[N];
int cnt[N];
int dengcha=0;
int kind=0;
int ans[N];
int L,R,block=sqrt(N);
void add1(int x)
{
    if(cnt[aa[x]]==0)
    {
        dengcha++;
        kind++;
    }
    else
    {
        if(fr[x]<=R&&fr[bak[x]]>R) dengcha--;
    }
    cnt[aa[x]]++;
}
void remov1e(int x)
{
    if(cnt[aa[x]]==1)
    {
        dengcha--;
        kind--;
    }
    else
    {
        if(fr[x]<=R&&fr[bak[x]]>R) dengcha++;
    }
    cnt[aa[x]]--;
}
void add2(int x,int l)
{
    if(cnt[aa[x]]==0)
    {
        dengcha++;
        kind++;
    }
    else
    {
        if(fl[x]>=l&&fl[pre[x]]<l) dengcha--;
    }
    cnt[aa[x]]++;
}
void remov2e(int x,int l)
{
    if(cnt[aa[x]]==1)
    {
        dengcha--;
        kind--;
    }
    else
    {
        if(fl[x]>=l&&fl[pre[x]]<l) dengcha++;
    }
    cnt[aa[x]]--;
}
void query(int x,int y,int flag)
{
    if (flag)
    {
        while(L>=x)
        {
            add1(L-1);
            L--;
        }
        while(L<x)
        {
            remov1e(L);
            L++;
        }
        while(R>y)
        {
            remov2e(R,x);
            R--;
        }
        while(R<y)
        {
            add2(R+1,x);
            R++;
        }
    }
    else
    {
        for (int i=x;i<=y;i++)
        {
            if(cnt[aa[i]]==0)
            {
                dengcha++;
                kind++;
            }
            else
            {
                if (fl[i]>=x&&fl[pre[i]]<x) dengcha--;//fl[i]>=x   指 i位置往左第一个构不成等差序列的位置在区间内， fl[pre[i]]<x 指 pre[i]位置往左第一个构不成等差序列的位置不在区间内，（防止重复计算）
            }
            cnt[aa[i]]++;
        }
        L=x,R=y;
    } 
}
void init()
{
    int i; 
    kind = 0;
    for (i=1; i<=m; i++)            //预处理
    {
        scanf("%d",&aa[i]);
        pre[i]=last[aa[i]];
        last[aa[i]]=i;
        if (pre[pre[i]]-pre[i]==pre[i]-i||pre[i]==0)
            fl[i]=fl[pre[i]];
        else fl[i]=pre[pre[i]];
    }
    fill(last,m+last,m+1);
    for (i=m; i>=1; i--)
    {
        bak[i]=last[aa[i]];
        last[aa[i]]=i;
        if (bak[bak[i]]-bak[i]==bak[i]-i||bak[i]==m+1)
            fr[i]=fr[bak[i]];
        else fr[i]=bak[bak[i]];
    }
}
int main()
{ 
    int m,i,j,qq,;
    cin>>m;
    init(); 
    scanf("%d",&qq);
    
    for (i=0;i<qq; i++)
    {
        scanf("%d%d",&q[i].x,&q[i].y);
        q[i].l=q[i].x/block_size;
        q[i].p=i;
    }
    sort(q,q+qq,cmp); 
    for (i=0;i<qq;i++)
    {
        query(q[i].x,q[i].y, i);
        ans[q[i].p]=kind+1;
        if (dengcha>0) 
            ans[q[i].p]--;
    } 
    for (i=0;i<qq;i++) 
        printf("%d\n",ans[i]);

    return 0;

}