1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
struct Seg{
long long mi, ma, miv, mav;
Seg *left, *right;
Seg(vector<long long>& A, long long l, long long r) : mi(A[l]), ma(A[r]), miv(INT_MAX), mav(0), left(nullptr), right(nullptr) {
if(l != r) {
long long m = l + (r - l) / 2;
left = new Seg(A,l,m);
right = new Seg(A,m+1,r);
}
}
void update(long long n, long long v) {
if(mi <= n and n <= ma) {
miv = min(miv,v);
mav = max(mav,v);
if(left) left->update(n,v);
if(right) right->update(n,v);
}
}
long long minQuery(long long n) {
if(mi > n) return miv;
if(ma <= n) return INT_MAX;
return min((left ? left->minQuery(n) : INT_MAX), (right ? right->minQuery(n) : INT_MAX));
}
long long maxQuery(long long n) {
if(mi > n) return mav;
if(ma <= n) return 0ll;
long long res = max((left ? left->maxQuery(n) : 0ll), (right ? right->maxQuery(n) : 0ll));
return res;
}
};
int Solution::maxSpecialProduct(vector<int> &A) {
vector<long long> S;
for(auto a : A) S.push_back(a);
sort(begin(S), end(S));
S.erase(unique(begin(S), end(S)), end(S));
Seg* lseg = new Seg(S, 0, S.size() - 1);
vector<long long> left(A.size());
for(int i = 0; i < A.size(); i++) {
left[i] = lseg->maxQuery(A[i]);
lseg->update(A[i], i);
}
long long res = 0, mod = 1e9 + 7;
Seg* rseg = new Seg(S, 0, S.size() - 1);
for(int i = A.size() - 1; i >= 0; i--) {
long long r = rseg->minQuery(A[i]);
if(r != INT_MAX) res = max(res, left[i] * r);
rseg->update(A[i],i);
}
return res % mod;
}
|
