[HDK - NRC] Sqen Paradox
题目描述
给定一个长度为 \(n\) 的数列 \(S\).
询问在给定区间 \([l,r]\) 内最长的没有重复元素的区间长度.
输入格式
第一行两个整数 \(n,m\).
第二行 \(n\) 个整数，描述数列 \(S\).
随后 \(m\) 行，每行一个询问.
输出格式
\(m\) 行，请你对每个询问操作输出一行答案.
样例 #1
样例输入 #1
5 3
1 2 3 3 4
1 3
2 4
1 5
样例输出 #1
3
2
3
提示
样例解释
-
询问
1 3，连续的最长区间为 \([1,3]\). -
询问
2 4，区间为 \([2,3]\). -
询问
1 5，区间为 \([1,3]\).
数据约定
输入数据满足 \(n,m\le 10^{5},S_{i}\le 10^{9}\).
解析
（以下做法来自 \(GGrun\)）
题干很简单，乍一看线段树呀，分块呀等数据结构。
但其实这道题要简单的多。
既然 找"没有重复元素的"区间，那么我们可以维护一个类似前缀的东西。
也就是找出每个点能向左延长多少。
所以只需要找出最后一个出现重复的数据就好了。
如图，\(1...6\) 前面都没有和自己重复的，直到又碰到一个 \(4\) ，
\(7\) 前面虽然没有和自己重复的，但是前面有一对 \(4\) ，所以只能到 \(4\) 。
综上：记录一个 \(k\) ，表示 最大长度只能为 \(k+1...i\) ，和每一个数上一次出现的位置。
取最大值更新 \(k\) ，就好啦！
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
int n,m,s[N],tot;
int cnt[N],qian[N];
map<int,int> mp;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
if(mp.find(s[i])==mp.end()) mp[s[i]]=++tot,s[i]=tot;
else s[i]=mp[s[i]];
}
int k=0;
for(int i=1;i<=n;i++)
{
k=max(k,cnt[s[i]]); cnt[s[i]]=i;
qian[i]=k;
}
while(m--)
{
int ans=1;
int x,y;
scanf("%d%d",&x,&y);
for(int i=x;i<=y;i++)
{
ans=max(ans,i-max(x-1,qian[i]));
}
printf("%d\n",ans);
}
return 0;
}