信息学奥赛一本通 1543：【例 3】与众不同

【题目链接】

ybt 1543：【例 3】与众不同

【题目考点】

1. RMQ问题

解决方法：

• ST表
• 线段树

2. 二分查找

3. 散列数组

【解题思路】

“完美序列”就是不重复元素构成的子段。以下将“完美序列”称为“不重复子段”
该题抽象后为：给定整数序列，每次查询一个区间中的最长不重复子段的长度。
设整个整数序列为a序列。
根据求最长上升子序列的经验，我们可以先求出以$a_i$为结尾的最长不重复子段的长度，如果知道了子段的右端点$i$与子段长度，子段的左端点（起始位置）自然也可以求出。
设数组$len$，$le{n}_i$表示以$a_i$为结尾的最长不重复子段的长度。
设数组$st$，$s{t}_i$表示以$a_i$为结尾的最长不重复子段的起始位置。
以$a_i$为结尾的最长不重复子段一定不会包括a序列中$a_i$前面的与$a_i$相等的元素，需要能够取到每个元素前面与其相等的元素的下标。
设数组$last$，$las{t}_i$表示数值i上一次出现的下标。
注意：输入的数值范围为$|a_i|\le 10^6$，即$-10^6\le a_i\le 10^6$，可能为负数。我们需要将输入的数值都增加$10^6$，使$0\le a_i\le 2\ast 10^6$，这样数值就可以作为$last$数组的下标了。（或者也可以将$a$序列离散化，或将last设为map）。
考虑求$s{t}_i$的递推式：
首先，以$a_i$为结尾的最长不重复子段的起始位置一定大于$las{t}_{a_i}$，即大于等于$las{t}_{a_i}+1$。
以$a_{i-1}$为结尾的最长不重复子段，肯定是由不重复元素构成的，其起始位置为$s{t}_{i-1}$。可以取其部分子段与$a_i$构成以$a_i$为结尾的最长不重复子段。

• 如果$s{t}_{i-1}\ge las{t}_{a_i}+1$，那么$s{t}_{i-1}$就是以$a_i$为结尾的最长不重复子段的起始位置$s{t}_i$。(因为第$s{t}_{i-1}$元素的前一个元素一定与以$a_{i-1}$为结尾的最长不重复子段中的某元素相同）。
• 如果$s{t}_{i-1}<las{t}_{a_i}+1$，那么$las{t}_{a_i}+1$就是以$a_i$为结尾的最长不重复子段的起始位置$s{t}_i$。(因为第$las{t}_{a_i}+1$元素的前一个元素$a_{las{t}_{a_i}}$与$a_i$相同）。

因此有： s t i = max ⁡ { s t i − 1 , l a s t a i + 1 } st_i=\max\{st_{i-1}, last_{a_i}+1\} sti​=max{sti−1​,lastai​​+1}。
显然，st数组是升序的。
求出st数组后，已知最长不重复子段的右端点和左端点，自然可以求出子段长度，即len数组。$le{n}_i=i-s{t}_i+1$

想要求区间$[l,r]$中最长不重复子段的长度。
以区间$[l,r]$中元素$a_i$为结尾的最长不重复子段有两类：子段起始位置$s{t}_i<l$，或子段起始位置$s{t}_i\ge l$。
由于$st$是升序的，那么区间$[l,r]$中一定存在一个位置$p$，使得：

• 当$i\in [l,p]$时，$s{t}_i<l$。
• 当$i\in [p+1,r]$时，$s{t}_i\ge l$

在升序序列$st$中求满足$s{t}_i<l$的最大的下标$p$，可以通过二分查找完成。
找到$p$后：

• 对于$i\in [l,p]$，由于$s{t}_i<l$，在$[l,r]$内以$a_i$为结尾的最长不重复子段的起始位置都是$l$，自然子段$[l,p]$的长度最长，长度为$p-l+1$
• 对于$i\in [p+1,r]$，由于$s{t}_i\ge l$，在$[l,r]$内以$a_i$为结尾的最长不重复子段的起始位置为$s{t}_i$，长度为$le{n}_i$，其中最长的不重复子段的长度为$len$序列区间$[p+1,r]$的最大值。
  求$len$序列的区间最值，可以对len序列建立ST表，每次区间查询的复杂度为$O(1)$。或建立线段树，每次区间查询的复杂度为$O(\log n)$，完成多次区间查询。
• 比较$p-l+1$和$len$序列区间$[p+1,r]$中的最大值，求出二者的最大值，即为区间$[l,r]$范围内最长不重复子段的长度。

注意：

1. 当二分查找找到的$p=r$时，区间$[p+1,r]$是不存在的，查询$len$序列区间$[p+1,r]$中的最大值，应该让这一次查询返回0，这样可以不影响结果。
2. 输入的查询区间$[l,r]$的左右端点l与r都是从0开始的，本代码下标都是从1开始的，因此需要将l和r都增加1。

【题解代码】

解法1：ST表

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define LN 25
int a[N], last[2000005], st[N], len[N], f[N][LN], lg[N];
void initST(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;//lg[i]：log_2(i)向下取整 for(int i = 1; i <= n; ++i)f[i][0] = len[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
int query(int l, int r)
{if(l > r)//本题中当p为r时，传入p+1, r，会出现形参l>r的情况，该情况非法，返回长度0。 return 0;int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;for(int i = 1; i <= n; ++i)//变为1~n {cin >> a[i];a[i] += 1000000;//输入的数值可能为负数，数值绝对值<=1e6，加上1e6后就是非负整数。 }for(int i = 1; i <= n; ++i){ st[i] = max(st[i-1], last[a[i]]+1);//st[i]：以a[i]为结尾的最长不重复子段的起始下标位置len[i] = i-st[i]+1;//len[i]：以a[i]为结尾的最长不重复子段的长度 last[a[i]] = i;//last[i]：数值i上一次出现的下标位置}initST(n);while(m--){cin >> l >> r;l++, r++;//变为从1开始int p = lower_bound(st+l, st+r+1, l)-st-1;cout << max(p-l+1, query(p+1, r)) << '\n';//query(p, r)：使用ST表求len[p]~len[r]的最大值 }return 0;
}

解法2：线段树

#include<bits/stdc++.h>
using namespace std;
#define N 200005
struct Node
{int l, r, val;
} tree[4*N];
int a[N], st[N], len[N];
map<int, int> last;
void pushUp(int i)
{tree[i].val = max(tree[2*i].val, tree[2*i+1].val);
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r){tree[i].val = len[l];return;}int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].r < l || tree[i].l > r)return 0;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return max(query(2*i, l, r), query(2*i+1, l, r));
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r, p;cin >> n >> m;for(int i = 1; i <= n; ++i)//变为1~n cin >> a[i];for(int i = 1; i <= n; ++i){ st[i] = max(st[i-1], last[a[i]]+1);//st[i]：以a[i]为结尾的最长不重复子段的起始下标位置len[i] = i-st[i]+1;//len[i]：以a[i]为结尾的最长不重复子段的长度 last[a[i]] = i;//last[i]：数值i上一次出现的下标位置}build(1, 1, n);while(m--){cin >> l >> r;l++, r++;//变为从1开始int tl = l, tr = r;//二分找满足st[i]<l的最大的i while(tl < tr){int mid = (tl+tr+1)/2;if(st[mid] < l)tl = mid;elsetr = mid-1;}p = tl;cout << max(p-l+1, query(1, p+1, r)) << '\n';//query(p, r)：使用ST表求len[p]~len[r]的最大值 }return 0;
}