专栏文章

区间最长连续不重复子序列

GGWOI
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodvyk6
此快照首次捕获于
2025/12/02 17:36
3 个月前
此快照最后确认于
2025/12/02 17:36
3 个月前
查看原文
题目链接

弱化版

给定一个长度为 NN 的序列 AA.
求 l,rl, r 满足 Al∼ArA_l \sim A_r 互不相同。你需要最大化 r−l+1r - l + 1 并输出 r−l+1r - l + 1。
如果有多个解输出其中 ll 最小的那个。

弱化版题解

弱化版有多种解法，如二分答案长度，双指针，可以在 O(nlog⁡n)O(n\log n) 甚至 O(n)O(n) 的时间复杂度内解决。
二分答案写法：二分一个长度 lenlen，每次 O(n)O(n) 的检查这个 lenlen 是否合法。容易发现 lenlen 有单调性。时间复杂度 O(nlog⁡n)O(n \log n)
双指针写法：每次 rr 增加 11，并将 ll 移动至最左边的合法的位置。容易发现 ll 单调不降，时间复杂度 O(n)O(n)。
使用弱化版的 O(nlog⁡n)O(n \log n) 的做法可以通过强化版 48pts48pts 的数据，使用弱化版 O(n)O(n) 的做法可以通过强化版 60pts60pts 的数据。

强化版

强化版在线做法

设 fif_i 表示以 ii 左端点，能取得的最右端点。并多维护一个 gig_i 表示以 ii 为左端点能取到的最长长度。
我们记录每一位的前驱，preipre_i 表示 ii 以前最大的 jj 且 Aj=AiA_j = A_i，这是可以 O(n)O(n) 求解的。
对于每一个 ii，我们现在知道了 [i,n][i, n] 的所有 prepre 值，我需要找个一个最大的 xx 满足 max⁡j=uxprej<i\max_{j = u}^x pre_j < i。因为左端点为定的 max⁡\max 数组有单调性，所以可以二分。最后 fi=x,gi=x−i+1f_{i} = x, g_{i} = x - i + 1。
这时候，使用第一个线段树或 st 表维护区间内 prepre 的最大值。
注意到 ff 数组是非严格单调递增的。
证明：ff 数组是非严格单调递增的。
若 ∃i<j,fi>fj\exists i < j, f_{i} > f_{j}，那么发现区间 [i,fi]⊆[j,fj][i, f_{i}] \subseteq [j, f_{j}] 且 AA 在区间 [i,fi][i, f_{i}] 没有重复的元素。那么此时 fjf_{j} 最大可以取到 fif_i 而非原本的 fjf_j。
证毕。
对于每一次询问 L,RL, R，我们需要找到最左边的 x(L≤x≤R)x(L \le x \le R) 满足 fx>Rf_x > R，那么 [x,R][x, R] 区间内的贡献最大也是在位置 xx 时，此时贡献为 R−x+1R - x + 1。
我们再求出 gg 在区间 [L,x−1][L, x - 1] 的最大值即可。
这时候，使用第二个线段树或 st 表维护区间内 gg 的最大值。
CPP
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define low_bit(x) ((x)&-(x))
//#define min(a,b) ((a)<(b)?(a):(b))
//#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
using ll = long long;
const int N = 2e5 + 5, M = 1e5 + 5;

int n, q, a[N];
int f[N], g[N], pre[N], d[M];
int t1[N << 2], t2[N << 2];
// zt = 1, 2 分别表示 g, pre 

void push_up(int num, int zt){
	if(zt == 1)	t1[num] = max(t1[num << 1], t1[num << 1 | 1]);
	if(zt == 2)	t2[num] = max(t2[num << 1], t2[num << 1 | 1]);
}

void build(int num, int l, int r, int zt){
	if(l == r){
		if(zt == 1)	t1[num] = g[l];
		if(zt == 2)	t2[num] = pre[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(num << 1, l, mid, zt);
	build(num << 1 | 1, mid + 1, r, zt);
	push_up(num, zt);
}

int qry(int num, int l, int r, int L, int R, int zt){
	if(l > R || r < L)	return 0;
	if(L <= l && r <= R){
		if(zt == 1)	return t1[num];
		return t2[num];
	}
	int mid = (l + r) >> 1;
	return max(qry(num << 1, l, mid, L, R, zt), qry(num << 1 | 1, mid + 1, r, L, R, zt));
}

bool check(int l, int x){// 需要 pre 在 [l, x] 的最大值 < l 
	return qry(1, 1, n, l, x, 2) < l;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
//	freopen("015.in", "r", stdin);
//	freopen("015.out", "w", stdout); 
	cin>>n;
	for(int i = 1;i <= n;i++)	cin>>a[i];
	for(int i = 1;i <= n;i++){
		pre[i] = d[a[i]];
		d[a[i]] = i;
	} 
	build(1, 1, n, 2);
	for(int i = n;i >= 1;i--){
		int l = i + 1, r = n, ans = i;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(check(i, mid))	l = mid + 1, ans = mid;
			else	r = mid - 1;
		}
		f[i] = ans;
		g[i] = ans - i + 1;
	}
	build(1, 1, n, 1);
	cin>>q;
	while(q--){
		int x, y;	cin>>x>>y;
		assert(1 <= x && x <= n && 1 <= y && y <= n);
		int l = x, r = y, p = y + 1;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(f[mid] > y)	r = mid - 1, p = mid;
			else	l = mid + 1;
		}
		int ans = 0;
		if(p != y + 1){
			ans = y - p + 1;
			if(p == x){
				cout<<ans<<'\n';
				continue;
			}
		}
		cout<<max(qry(1, 1, n, x, p - 1, 1), ans)<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...