A. [CF522D] Closest Equals
显然只有 \(O(n)\) 个数对（相邻的相同点）有可能对答案产生贡献，拉出来二维数点即可 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,tot,c[N],ans[N];
unordered_map<int,int>mp;
struct msq{int x,y,op;
}cc[N*2];
inline bool cmp(msq x,msq y){return x.x!=y.x?x.x<y.x:x.y!=y.y?x.y<y.y:x.op<y.op;
}
inline void init(){for(int i=1;i<=n;i++) c[i]=1e9;
}
inline void add(int x,int v){for(;x<=n;x+=x&-x) c[x]=min(c[x],v);
}
inline int minn(int x){int re=1e9;for(;x;x-=x&-x) re=min(re,c[x]);return re;
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m,init();for(int i=1,a;i<=n;i++){cin>>a;if(mp.count(a))cc[++tot]={n-mp[a]+1,i,mp[a]-i};mp[a]=i;}for(int i=1,l,r;i<=m;i++)cin>>l>>r,cc[++tot]={n-l+1,r,i};sort(cc+1,cc+tot+1,cmp);for(int i=1;i<=tot;i++){if(cc[i].op>0) ans[cc[i].op]=minn(cc[i].y);else add(cc[i].y,-cc[i].op);}for(int i=1;i<=m;i++)cout<<(ans[i]==1e9?-1:ans[i])<<"\n";return 0;
}
C. [Ynoi Easy Round 2023] TEST_107
和 A 一样的地方在于都有一个贡献是由相邻的相同点构成的，同样用二维数点处理，不同的地方在于还需要维护每种颜色在一段区间内的第一个位置和最后一个位置，扫描线即可 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
template<typename T>
inline void read(T &x){x=0;char c=getchar();bool fl=0;while(c>57||c<48) fl=(c=='-'),c=getchar();while(c>=48&&c<=57)x=(x<<1)+(x<<3)+c-48,c=getchar();x=(fl?-x:x);
}
template<typename T>
inline void write(T x){if(x<0) x=-x,putchar('-');if(x>9) write(x/10);putchar(x%10+48);
}
const int N=2e6+5;
int n,m,a[N],ls[N],lc[N],rc[N],ans[N];
vector<int>qua[N],qub[N];
int mn[N<<2];
inline void build(int x,int l,int r){mn[x]=1e9;if(l==r) return;int mid=(l+r)>>1;build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
inline void chgn(int x,int l,int r,int k,int v){if(l==r){mn[x]=v;return;}int mid=(l+r)>>1;if(k<=mid) chgn(x<<1,l,mid,k,v);else chgn(x<<1|1,mid+1,r,k,v);mn[x]=min(mn[x<<1],mn[x<<1|1]);
}
inline int minn(int x,int l,int r,int L){if(L<=l) return mn[x];int mid=(l+r)>>1;int re=minn(x<<1|1,mid+1,r,L);if(L<=mid) re=min(re,minn(x<<1,l,mid,L));return re;
}
int mx[N<<2];
inline void chgx(int x,int l,int r,int k,int v){if(l==r){mx[x]=v;return;}int mid=(l+r)>>1;if(k<=mid) chgx(x<<1,l,mid,k,v);else chgx(x<<1|1,mid+1,r,k,v);mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
inline int maxn(int x,int l,int r,int R){if(R>=r) return mx[x];int mid=(l+r)>>1;int re=maxn(x<<1,l,mid,R);if(mid<R) re=max(re,maxn(x<<1|1,mid+1,r,R));return re;
}
int tot,c[N];
struct lxl{int x,y,id;
}xlx[N<<1];
inline bool cmp(lxl x,lxl y){return x.x!=y.x?x.x<y.x:x.y!=y.y?x.y<y.y:x.id<y.id;
}
inline void add(int x,int v){for(;x<=n;x+=x&-x) c[x]=max(c[x],v);
}
inline int maxx(int x){int re=0;for(;x;x-=x&-x) re=max(re,c[x]);return re;
}
int main(){read(n),read(m);for(int i=1;i<=n;i++) read(a[i]);for(int i=1;i<=m;i++){read(lc[i]),read(rc[i]);qua[rc[i]].push_back(i);qub[lc[i]].push_back(i);xlx[++tot]={n-lc[i]+1,rc[i],i};}build(1,1,2e6);for(int i=1;i<=n;i++){if(ls[a[i]]){chgn(1,1,2e6,ls[a[i]],1e9);xlx[++tot]={n-ls[a[i]]+1,i,ls[a[i]]-i+1};}chgn(1,1,2e6,i,i),ls[a[i]]=i;for(int j:qua[i])ans[j]=max(i-minn(1,1,2e6,lc[j]),0);}for(int i=1;i<=2e6;i++) ls[i]=0;for(int i=n;i;i--){if(ls[a[i]])chgx(1,1,2e6,ls[a[i]],0);chgx(1,1,2e6,i,i),ls[a[i]]=i;for(int j:qub[i])ans[j]=max(maxn(1,1,2e6,rc[j])-i,ans[j]);}sort(xlx+1,xlx+tot+1,cmp);for(int i=1;i<=tot;i++){if(xlx[i].id<=0) add(xlx[i].y,-xlx[i].id);else ans[xlx[i].id]=max(ans[xlx[i].id],maxx(xlx[i].y));}for(int i=1;i<=m;i++)write(ans[i]),putchar('\n');return 0;
}