题目： 题意：给定序列，求[l,r]区间内数字相同的数的最远距离。
链接：https://www.codechef.com/problems/QCHEF
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define dep(i,j,k) for(int i=k;i>=j;i--) #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define make(i,j) make_pair(i,j) #define pb push_back using namespace std; const int N=1e5+10; int a[N],pos[N],mi[N],ma[N],t[N],ans[N],n,m,k,block,tmp; struct noq { int l,r,id; }q[N]; bool cmp(noq a,noq b) { return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l]; } void add(int x) { mi[a[x]]=min(mi[a[x]],x); ma[a[x]]=max(ma[a[x]],x); tmp=max(tmp,ma[a[x]]-mi[a[x]]); } int query(int l,int r) { int mx=0; rep(j,l,r) t[a[j]]=0x3f3f3f3f; rep(j,l,r){ t[a[j]]=min(t[a[j]],j); mx=max(mx,j-t[a[j]]); } return mx; } int slove(int qnum,int bnum) { int i=qnum; int L=min(bnum*block,n); int l=L+1,r=L; mem(ma,-63); mem(mi,63); tmp=0; for(;pos[q[i].l]==bnum;i++) { if(pos[q[i].l]==pos[q[i].r]) { ans[q[i].id]=query(q[i].l,q[i].r); continue; } while(r<q[i].r) add(++r); int mx=0; rep(j,q[i].l,l) t[a[j]]=0x3f3f3f3f; rep(j,q[i].l,l) { t[a[j]]=min(t[a[j]],j); mx=max(mx,max(j-t[a[j]],ma[a[j]]-j)); } ans[q[i].id]=max(mx,tmp); } return i; } int main() { scanf("%d %d %d",&n,&m,&k); block=sqrt(n); rep(i,1,n) { scanf("%d",&a[i]); pos[i]=(i-1)/block+1; } rep(i,1,k) { scanf("%d %d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+k,cmp); int up=pos[k]; int p=1; rep(i,1,up) p=slove(p,i); rep(i,1,k) printf("%d ",ans[i]); return 0; }