数组(array)

问题 C: 数组(array)
时间限制: 3 Sec 内存限制: 512 MB

题目描述
给定包含n个正整数的数组Ai亚博竞猜APPwww.yabox3.com亚博yabo线上投注" role="presentation" style="position: relative;">Ai,有m" role="presentation" style="position: relative;">m个询问,每次询问一段区间内最远的两个相同的数的距离,即最大化yx" role="presentation" style="position: relative;">y?x,满足Ax=Ay" role="presentation" style="position: relative;">Ax=Ay,LixyRi" role="presentation" style="position: relative;">LixyRi
特别地,如果区间内不存在两个相同的数,输出0。
输入
第一行3" role="presentation" style="position: relative;">3个正整数n" role="presentation" style="position: relative;">n,k" role="presentation" style="position: relative;">k,m" role="presentation" style="position: relative;">m,分别表示数组长度,数组中每个数的最大值和询问个数。
接下来一行n" role="presentation" style="position: relative;">n个正整数Ai" role="presentation" style="position: relative;">Ai1Aik" role="presentation" style="position: relative;">1Aik
接下里m" role="presentation" style="position: relative;">m行,每行两个正整数Li" role="presentation" style="position: relative;">Li,Ri" role="presentation" style="position: relative;">Ri,描述一组询问。
输出
对于每个询问,输出一行答案。
样例输入
7 7 5
4 5 6 6 5 7 4
6 6
5 6
3 5
3 7
1 7
样例输出
0
0
1
1
6
提示

题解:
这题应该还是比较裸的,直接分块+暴力(莫队)即可。
Code:

#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int n,k,m,t,res,ans;
int a[N],L[N],R[N],l[N],r[N],Ans[N];
struct note
{
    int l,r,k,id;
}Q[N];
bool cmp(note a,note b)
{
    if(a.k!=b.k)return a.kreturn a.rint main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int sq=(int)sqrt(n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&Q[i].l,&Q[i].r);
        Q[i].k=(Q[i].l-1)/sq+1;
        Q[i].id=i;
    }
    sort(Q+1,Q+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(Q[i].k!=Q[i-1].k)
        {
            res=0;
            for(int j=0;j<=k;j++)
            {
                L[j]=l[j]=-1;
                R[j]=r[j]=n+1;
            }
            t=sq*Q[i].k;
        }
        while(tif(L[a[t]]==-1)L[a[t]]=l[a[t]]=t;
            if(R[a[t]]!=L[a[t]])
                res=max(res,R[a[t]]-L[a[t]]);
        }
        ans=res;
        for(int j=min(sq*Q[i].k,Q[i].r);j>=Q[i].l;j--)
        {
            l[a[j]]=j;
            if(r[a[j]]==n+1)r[a[j]]=j;
            if(r[a[j]]!=l[a[j]])
                ans=max(ans,r[a[j]]-l[a[j]]);
        }
        for(int j=min(sq*Q[i].k,Q[i].r);j>=Q[i].l;j--)
        {
            l[a[j]]=L[a[j]];
            r[a[j]]=R[a[j]];
        }
        Ans[Q[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",Ans[i]);
    return 0;
}