安阳网站怎么优化,公众号怎么制作微信红包封面,wordpress 滑动解锁,站长之家seo工具包【题目链接】
ybt 1543#xff1a;【例 3】与众不同
【题目考点】
1. RMQ问题
解决方法#xff1a;
ST表线段树
2. 二分查找
3. 散列数组
【解题思路】
“完美序列”就是不重复元素构成的子段。以下将“完美序列”称为“不重复子段” 该题抽象后为#xff1a;给定整…【题目链接】
ybt 1543【例 3】与众不同
【题目考点】
1. RMQ问题
解决方法
ST表线段树
2. 二分查找
3. 散列数组
【解题思路】
“完美序列”就是不重复元素构成的子段。以下将“完美序列”称为“不重复子段” 该题抽象后为给定整数序列每次查询一个区间中的最长不重复子段的长度。 设整个整数序列为a序列。 根据求最长上升子序列的经验我们可以先求出以 a i a_i ai为结尾的最长不重复子段的长度如果知道了子段的右端点 i i i与子段长度子段的左端点起始位置自然也可以求出。 设数组 l e n len len l e n i len_i leni表示以 a i a_i ai为结尾的最长不重复子段的长度。 设数组 s t st st s t i st_i sti表示以 a i a_i ai为结尾的最长不重复子段的起始位置。 以 a i a_i ai为结尾的最长不重复子段一定不会包括a序列中 a i a_i ai前面的与 a i a_i ai相等的元素需要能够取到每个元素前面与其相等的元素的下标。 设数组 l a s t last last l a s t i last_i lasti表示数值i上一次出现的下标。 注意输入的数值范围为 ∣ a i ∣ ≤ 10 6 |a_i|\le 10^6 ∣ai∣≤106即 − 10 6 ≤ a i ≤ 10 6 -10^6\le a_i \le 10^6 −106≤ai≤106可能为负数。我们需要将输入的数值都增加 10 6 10^6 106使 0 ≤ a i ≤ 2 ∗ 10 6 0\le a_i\le 2*10^6 0≤ai≤2∗106这样数值就可以作为 l a s t last last数组的下标了。或者也可以将 a a a序列离散化或将last设为map。 考虑求 s t i st_i sti的递推式 首先以 a i a_i ai为结尾的最长不重复子段的起始位置一定大于 l a s t a i last_{a_i} lastai即大于等于 l a s t a i 1 last_{a_i}1 lastai1。 以 a i − 1 a_{i-1} ai−1为结尾的最长不重复子段肯定是由不重复元素构成的其起始位置为 s t i − 1 st_{i-1} sti−1。可以取其部分子段与 a i a_i ai构成以 a i a_i ai为结尾的最长不重复子段。
如果 s t i − 1 ≥ l a s t a i 1 st_{i-1}\ge last_{a_i}1 sti−1≥lastai1那么 s t i − 1 st_{i-1} sti−1就是以 a i a_i ai为结尾的最长不重复子段的起始位置 s t i st_i sti。(因为第 s t i − 1 st_{i-1} sti−1元素的前一个元素一定与以 a i − 1 a_{i-1} ai−1为结尾的最长不重复子段中的某元素相同。如果 s t i − 1 l a s t a i 1 st_{i-1} last_{a_i}1 sti−1lastai1那么 l a s t a i 1 last_{a_i}1 lastai1就是以 a i a_i ai为结尾的最长不重复子段的起始位置 s t i st_i sti。(因为第 l a s t a i 1 last_{a_i}1 lastai1元素的前一个元素 a l a s t a i a_{last_{a_i}} alastai与 a i a_i ai相同。
因此有 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\} stimax{sti−1,lastai1}。 显然st数组是升序的。 求出st数组后已知最长不重复子段的右端点和左端点自然可以求出子段长度即len数组。 l e n i i − s t i 1 len_ii-st_i1 lenii−sti1
想要求区间 [ l , r ] [l, r] [l,r]中最长不重复子段的长度。 以区间 [ l , r ] [l, r] [l,r]中元素 a i a_i ai为结尾的最长不重复子段有两类子段起始位置 s t i l st_il stil或子段起始位置 s t i ≥ l st_i\ge l sti≥l。 由于 s t st st是升序的那么区间 [ l , r ] [l, r] [l,r]中一定存在一个位置 p p p使得
当 i ∈ [ l , p ] i\in[l, p] i∈[l,p]时 s t i l st_il stil。当 i ∈ [ p 1 , r ] i\in[p1,r] i∈[p1,r]时 s t i ≥ l st_i\ge l sti≥l
在升序序列 s t st st中求满足 s t i l st_il stil的最大的下标 p p p可以通过二分查找完成。 找到 p p p后
对于 i ∈ [ l , p ] i\in[l, p] i∈[l,p]由于 s t i l st_il stil在 [ l , r ] [l, r] [l,r]内以 a i a_i ai为结尾的最长不重复子段的起始位置都是 l l l自然子段 [ l , p ] [l, p] [l,p]的长度最长长度为 p − l 1 p-l1 p−l1对于 i ∈ [ p 1 , r ] i\in[p1, r] i∈[p1,r]由于 s t i ≥ l st_i\ge l sti≥l在 [ l , r ] [l, r] [l,r]内以 a i a_i ai为结尾的最长不重复子段的起始位置为 s t i st_i sti长度为 l e n i len_i leni其中最长的不重复子段的长度为 l e n len len序列区间 [ p 1 , r ] [p1, r] [p1,r]的最大值。 求 l e n len len序列的区间最值可以对len序列建立ST表每次区间查询的复杂度为 O ( 1 ) O(1) O(1)。或建立线段树每次区间查询的复杂度为 O ( log n ) O(\log n) O(logn)完成多次区间查询。比较 p − l 1 p-l1 p−l1和 l e n len len序列区间 [ p 1 , r ] [p1,r] [p1,r]中的最大值求出二者的最大值即为区间 [ l , r ] [l, r] [l,r]范围内最长不重复子段的长度。
注意
当二分查找找到的 p r pr pr时区间 [ p 1 , r ] [p1,r] [p1,r]是不存在的查询 l e n len len序列区间 [ p 1 , r ] [p1,r] [p1,r]中的最大值应该让这一次查询返回0这样可以不影响结果。输入的查询区间 [ l , r ] [l, r] [l,r]的左右端点l与r都是从0开始的本代码下标都是从1开始的因此需要将l和r都增加1。
【题解代码】
解法1ST表
#includebits/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(1j)-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时传入p1, r会出现形参lr的情况该情况非法返回长度0。 return 0;int k lg[r-l1];return max(f[l][k], f[r-(1k)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(stl, str1, l)-st-1;cout max(p-l1, query(p1, r)) \n;//query(p, r)使用ST表求len[p]~len[r]的最大值 }return 0;
}解法2线段树
#includebits/stdc.h
using namespace std;
#define N 200005
struct Node
{int l, r, val;
} tree[4*N];
int a[N], st[N], len[N];
mapint, int last;
void pushUp(int i)
{tree[i].val max(tree[2*i].val, tree[2*i1].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 (lr)/2;build(2*i, l, mid);build(2*i1, mid1, 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*i1, 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 (tltr1)/2;if(st[mid] l)tl mid;elsetr mid-1;}p tl;cout max(p-l1, query(1, p1, r)) \n;//query(p, r)使用ST表求len[p]~len[r]的最大值 }return 0;
}
