St Table + two points

subject :https://codeforces.ml/contest/1549/problem/D

ST surface :

1. Online modification is not supported Preprocessing event complexity 0(nlogn), Query events o(1)

2. For example, find the maximum value of a certain section st[i][j] From i To i+2^j

Then its maximum value is determined by the first half and the second half

The first half : by i+2^(j-1), The second half is (i+2^(j-1)+1)+2^(j-1)

that 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]);
}
}

Topic analysis ：

Carelessness : Find the longest subsequence in an interval , The values of this sequence are congruent m,m>=2

analysis ：

Congruence property :

If x ≡ y ( m o d p ) 
that ( x − y ) %p==0

So construct a difference array , Then, if the difference fraction group satisfying the interval is not coprime

AC Code :

#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];// representative k The scope of the 
ll n;
// Verify whether it is mutual prime 
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)// Find the optimal interval   Meet the requirements of mutual prime 
	{
		mid = l + r + 1 >> 1;
		if (abs(query(p, mid)) < 2)// Be careful abs Where to put it 
		{
			r = mid - 1;// Try to make the interval smaller 
		}
		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; } // After a k The value is always greater than the previous one 
	while (T--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		// Initialize the rest 
		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];// Build a differential array 
		}
		for (int i = 1; (1 << i) <= n; i++)//i It's state 
		{
			for (int j = 1; j + (1 << i) - 1 <= n; j++)//j Is the position 
			{
				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);// Third i+1 Save this location 
			if (u == 1)continue;// Mutual prime continues to extend 
			p = max(p, u - i + 1);
		}
		cout << p << endl;
	}
}