对于nlogn复杂度下动态维护GCD区间的思考 & 求题

在做题时发现的trick:P5502

我们都知道有一种在

O(n\log n)

的复杂度下动态维护GCD区间长度的套路：

CPP

vector<pair<int,int>> cur,nxt;
for 每个新元素x:
	nxt.clear();
	nxt.push_back({x,1}); // 新元素单独成段
	
	for 每个旧状态[g,len] in cur:
		new_g = gcd(g,x);
		if new_g == nxt.back().g:
			nxt.back().g = max(nxt.back().g,len+1);
		else:
			nxt.push_back({new_g,len+1});

	cur = nxt;
	更新答案

那么我们是否可以推广到以下形式中： (f需满足结合律：f(a,f(b,c)) = f((a,b),c) 才可以，常用的有：gcd、lcm、min、max、*、&、|、^)

CPP

vector<pair<int,int>> cur,nxt;
for 每个新元素x:
	nxt.clear();
	nxt.push_back({x,1}); // 新元素单独成段
	for 每个旧状态[val,len] in cur:
		new_val = f(new_val,val); // f需满足结合律：f(a,f(b,c)) = f((a,b),c) 才可以，如gcd, min, max等
		if new_val == nxt.back().g:
			合并长度
		else:
			创建新段

	cur = nxt;
	更新答案

这个套路除了可以解决最长区间问题外，还能解决什么问题？有没有推荐题单？求大佬解答

对于nlogn复杂度下动态维护GCD区间的思考 & 求题

讨论操作

回复

相关推荐

对于nlogn复杂度下动态维护GCD区间的思考 & 求题