U423621 [HDK - NRC] Sqen Paradox 题解

题目描述及 \(O(n^2)\) 做法见 这个

设 \(a_i\) 表示以 \(i\) 为左端点，无重复元素的最长区间的左端点，这个直接拿双指针做就行。

处理出来后，分类讨论，找 \(\max(i-l+1,i-a_i+1)\)，找 \(i-l+1\) 拿个桶维护一下左端点为 \(i\) 的右端点有那些就行，剩下的位置找最值即可，这个是 RMQ。时间复杂度为 \(O(n\log n)\) 瓶颈在 st 表，拿这个维护就 O(n) 了

AC record

#include<bits/stdc++.h>
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e6+10;
int a[N],temp[N],mp[N],n,m,tot,L[N],l=1,st[N][25],c[N];
std::vector<int> t[N];
std::unordered_map<int,int> map;
inline int ask(int l,int r){if(l>r)return 0;int k=std::__lg(r-l+1);return std::max(st[l][k],st[r-(1<<k)+1][k]);}
int main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read();m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		if(!map[a[i]])map[a[i]]=++tot;
		a[i]=map[a[i]];
		mp[a[i]]++;
		while(mp[a[i]]>1)mp[a[l++]]--;
		L[i]=l;
		t[L[i]].push_back(i);
	}
	for(int i=1;i<=n;++i)a[i]=i-L[i]+1,st[i][0]=a[i];
	for(int k=1;k<=std::__lg(n);++k)
		for(int i=1;i+(1<<k)-1<=n;++i)
			st[i][k]=std::max(st[i][k-1],st[i+(1<<k-1)][k-1]);
	for(int i=1;i<=n;++i){if(!t[i].size())c[i]=c[i-1];else c[i]=i;}
	for(int i=1;i<=m;++i){
		int l=read(),r=read(),res=0;
		if(l>r)std::swap(l,r);
		int zc=c[l];
		int mid=std::min(t[zc][t[zc].size()-1],r);
		std::cout<<std::max(mid-l+1,ask(mid+1,r))<<'\n';
	}
}

特别鸣谢：int_R