Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目大意是说，定义一个数的lucky number是距离i最远的j且满足（a[i]<a[j] i<j）。
问对所有数最大的lucky number是什么。
不必线段树。
我们可以先处理出a[i]的最远点。倒着扫一遍即可。
然后可以处理出大于等于a[i]的最远位置。
1/*************************************************************************
2 > File Name: code/hust/20151115/A.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年11月23日 星期一 22时13分15秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int N=1E5+6;
31typedef long long LL;
32int a[N];
33int n;
34int p[N];
35const int inf = 0x3f3f3f3f;
36int main()
37{
38 #ifndef ONLINE_JUDGE
39 freopen("in.txt","r",stdin);
40 #endif
41
42 int T;
43 scanf("%d",&T);
44 while (T--)
45 {
46 scanf("%d",&n);
47 int mx = -1;
48 for ( int i = 1 ; i <= n ; i++ ) scanf("%d",&a[i]),mx = max(mx,a[i]);
49
50
51 ms(p,-1);
52 for ( int i = 1 ; i <= n ; i++)
53 p[a[i]] = max(p[a[i]],i); //最远的a[i]的位置
54 for ( int i = mx ; i >= 1 ; i--)
55 p[i] = max(p[i],p[i+1]);//cout<<"p[i]:"<<p[i]<<endl; //最远的>= a[i]的位置
56
57 int ans = 0;
58 for ( int i = 1 ; i <= n ; i++)
59 ans = max(ans,p[a[i]+1]-i);
60 printf("%d\n",ans);
61
62 }
63
64
65
66
67 #ifndef ONLINE_JUDGE
68 #endif
69 fclose(stdin);
70 return 0;
71}