题目: 题意:给定序列,求[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\n",ans[i]);
return 0;
}
View Code