- 技术博客
- 1045 快速排序
思路：用big[i]记录前缀的最大值 sma[i]用来记录后缀的最大值，看一个数是否等于他的前缀最大值和后缀最小值即可，坑点：没有主元的时候要输出空行不能什么都不输出
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1000000007 ;
const int N
=2e6+10;
const int M
=1e3+10;
const int inf
=0x7f7f7f7f;
const int maxx
=2e5+7;
const double eps
=1e-6;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll
qsm(int a
,int b
,int p
)
{
ll res
=1%p
;
while(b
)
{
if(b
&1)
res
=res
*a
%p
;
a
=1ll*a
*a
%p
;
b
>>=1;
}
return res
;
}
int a
[N
];
int sma
[N
];
int big
[N
];
int main()
{
int n
;
scanf("%d",&n
);
sma
[n
+1]=inf
;
big
[0]=-inf
;
for(int i
=1;i
<=n
;i
++)
{
scanf("%d",&a
[i
]);
big
[i
]=max(big
[i
-1],a
[i
]);
}
for(int i
=n
;i
>=1;i
--)
{
sma
[i
]=min(sma
[i
+1],a
[i
]);
}
vector
<int> vt
;
for(int i
=1;i
<=n
;i
++)
{
if(big
[i
]==a
[i
]&&sma
[i
]==a
[i
])
vt
.push_back(a
[i
]);
}
sort(vt
.begin(),vt
.end());
int len
=vt
.size();
printf("%d\n",len
);
if(len
!=0)
{
for(int i
=0;i
<len
-1;i
++)
printf("%d ",vt
[i
]);
printf("%d",vt
[len
-1]);
}
else
printf("\n");
return 0;
}
