ST表+二分

题目:https://codeforces.ml/contest/1549/problem/D

ST表:

1.不支持在线修改 预处理事件复杂度0(nlogn),查询事件o(1)

2.例如求某一段最大值 st[i][j] 表示从i到i+2^j

那么它的最值则是由前一半和后一半决定

前一半:为i+2^(j-1),后一半则为(i+2^(j-1)+1)+2^(j-1)

那么st[i][j]=max(st[i][j-1],st[i][i+2^(j-1)+1][j-1])

for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)<=n+1;i++)
{
st[i][j]=max[st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}

题目分析：

大意:求一段区间内最长的子序列，其中这段序列的各个值同余m,m>=2

分析：

同余性质:

如果 x ≡ y ( m o d p ) 
那么( x − y ) %p==0

因此构造一个差分数组，然后满足区间的差分数组不互质就行

AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[212100];
ll st[212100][30];
ll lg2[212100];//代表k的范围
ll n;
//验证是否互质
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll query(ll l, ll r) { return gcd(st[l][lg2[r - l + 1]], st[r - (1 << lg2[r - l + 1]) + 1][lg2[r - l + 1]]); }
ll bsearch(ll l, ll r, ll p)
{
	ll mid;
	ll k = 1;
	while (l < r)//找出最优的区间 符合互质的要求
	{
		mid = l + r + 1 >> 1;
		if (abs(query(p, mid)) < 2)//注意abs放的位置
		{
			r = mid - 1;//尽量使得区间小一点
		}
		else
		{
			l = mid;
		}
	}
	if (abs(query(p, l)) < 2) { return 1; }
	return l;
}
int main()
{
	int T;
	cin >> T;
	lg2[0] = -1;
	for (int i = 2; i <= 210000; i++) { lg2[i] = lg2[i>>1] + 1; } //后一个k值总是比前面大一
	while (T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		//初始化剩余部分
		for (int i = n + 1; i <= 2 * n && i <= 200000; i++) { st[i][0] = 0; }
		for (int i = 1; i <= n; i++)
		{
			st[i][0] = a[i] - a[i - 1];//构建差分数组
		}
		for (int i = 1; (1 << i) <= n; i++)//i是状态
		{
			for (int j = 1; j + (1 << i) - 1 <= n; j++)//j是位置
			{
				st[j][i] = gcd(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
			}
		}
		ll p = 1;
		for (ll i = 1; i <= n; i++)
		{
			ll u = bsearch(i + 1, n, i + 1);//第三个i+1保存此时的位置
			if (u == 1)continue;//互质继续延长
			p = max(p, u - i + 1);
		}
		cout << p << endl;
	}
}