time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
When Xellos was doing a practice course in university, he once had to measure the intensity of an effect that slowly approached equilibrium. A good way to determine the equilibrium intensity would be choosing a sufficiently large number of consecutive data points that seems as constant as possible and taking their average. Of course, with the usual sizes of data, it’s nothing challenging — but why not make a similar programming contest problem while we’re at it?
You’re given a sequence of n data points a1, …, an. There aren’t any big jumps between consecutive data points — for each 1 ≤ i < n, it’s guaranteed that |ai + 1 - ai| ≤ 1.
A range [l, r] of data points is said to be almost constant if the difference between the largest and the smallest value in that range is at most 1. Formally, let M be the maximum and m the minimum value of ai for l ≤ i ≤ r; the range [l, r] is almost constant if M - m ≤ 1.
Find the length of the longest almost constant range.
Input
The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of data points.
The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 100 000).
Output
Print a single number — the maximum length of an almost constant range of the given sequence.
Examples
input
5
1 2 3 3 2
output
4
input
11
5 4 5 5 6 7 8 8 8 7 6
output
5
Note
In the first sample, the longest almost constant range is [2, 5]; its length (the number of data points in it) is 4.
In the second sample, there are three almost constant ranges of length 4: [1, 4], [6, 9] and [7, 10]; the only almost constant range of the maximum length 5 is [6, 10].
【题目链接】:http://codeforces.com/contest/602/problem/B
【题解】
用ST算法先搞出各个区间的最大、最小值
然后枚举区间的左端点、二分右端点.
判断依据就是最大值和最小值的差;
如果小于等于1则右端点可以再往右点。否则往左
一般用二分都能过吧。
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e5+100;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int n;
int a[MAXN];
int ma[MAXN][18],mi[MAXN][20];
int pre2[20];
int need[MAXN];
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
rei(a[i]),mi[i][0] = ma[i][0] = a[i];
pre2[0] = 1;
for (int i = 1; i <= 18; i++)
pre2[i] = pre2[i - 1] << 1;
need[1] = 0; need[2] = 1;
int temp = 2;
for (int i = 3; i <= n; i++)
if (pre2[temp] == i)
need[i] = need[i - 1] + 1, temp++;
else
need[i] = need[i - 1];
for (int l = 1; pre2[l] <= n; l++)
for (int i = 1;i <= n;i++)
if (i + pre2[l] - 1 <= n)
{
ma[i][l] = max(ma[i][l - 1], ma[i + pre2[l - 1]][l - 1]);
mi[i][l] = min(mi[i][l - 1], mi[i + pre2[l - 1]][l - 1]);
}
int ans = 0;
rep1(i,1,n)
{
int l = i,r = n,tempr=l;
while (l <= r)
{
int m = (l+r)>>1;
int le = need[m-i+1];
int mi1 = min(mi[i][le],mi[m-pre2[le]+1][le]);
int ma1 = max(ma[i][le],ma[m-pre2[le]+1][le]);
if (abs(mi1-ma1)<=1)
{
tempr = m;
l = m+1;
}
else
r = m-1;
}
if(tempr-i+1> ans)
ans = tempr-i+1;
}
cout << ans << endl;
return 0;
}
close