#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
struct SegmentTree{
vector<pair<int, int>>sTree;
void init(int n){
sTree.resize(4 * n);
}
void Build(int node, int l, int r, vector<int>&v){
if(l == r){
sTree[node] = {v[l], v[l]};
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid, v);
Build(node * 2 + 1, mid + 1, r, v);
sTree[node] = {min(sTree[node * 2].first, sTree[node * 2 + 1].first), max(sTree[node * 2].second, sTree[node * 2 + 1].second)};
}
}
int Min_Query(int node, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return sTree[node].first;
}
if(ql > r || l > qr)return 1e9;
int mid = (l + r) >> 1;
int lc = Min_Query(node * 2, l, mid, ql, qr);
int rc = Min_Query(node * 2 + 1, mid + 1, r, ql, qr);
return min(lc, rc);
}
int Max_Query(int node, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return sTree[node].second;
}
if(ql > r || l > qr)return 0;
int mid = (l + r) >> 1;
int lc = Max_Query(node * 2, l, mid, ql, qr);
int rc = Max_Query(node * 2 + 1, mid + 1, r, ql, qr);
return max(lc, rc);
}
};
struct MergeSortTree{
vector<vector<int>>mTree;
void init(int n){
mTree.resize(4 * n);
}
vector<int> Merge(vector<int>&left, vector<int>&right){
vector<int>res;
int p1 = 0, p2 = 0;
while(p1 < left.size() || p2 < right.size()){
if(p1 == left.size()){
res.push_back(right[p2++]);
}
else if(p2 == right.size()){
res.push_back(left[p1++]);
}
else if(left[p1] > right[p2]){
res.push_back(right[p2++]);
}
else{
res.push_back(left[p1++]);
}
}
return res;
}
void Build(int node, int l, int r, vector<int>&v){
if(l == r){
mTree[node].push_back(v[l]);
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid, v);
Build(node * 2 + 1, mid + 1, r, v);
mTree[node] = Merge(mTree[node * 2], mTree[node * 2 + 1]);
}
}
int Query(int node, int l, int r, int ql, int qr, int num1, int num2){
if(ql <= l && r <= qr){
auto itr1 = upper_bound(mTree[node].begin(), mTree[node].end(), num1);
auto itr2 = lower_bound(mTree[node].begin(), mTree[node].end(), num2);
itr2--;
int pos1 = itr1 - mTree[node].begin();
int pos2 = itr2 - mTree[node].begin();
return max(0, itr2 - itr1 + 1);
}
if(ql > r || l > qr)return 0;
int mid = (l + r) >> 1;
int lc = Query(node * 2, l, mid, ql, qr, num1, num2);
int rc = Query(node * 2 + 1, mid + 1, r, ql, qr, num1, num2);
return lc + rc;
}
};
SegmentTree tree;
MergeSortTree mtree;
/*
6
3 6 4 5 1 2
*/
int rec(int indx){
int res = 1e9, mn = 1e9, mx = 0;
if(indx == n + 1)return 0;
for(int i = indx;i <= n;++i){
mn = min(mn, v[i]);
mx = max(mx, v[i]);
int MN = tree.Min_Query(1, 1, n, 1, indx - 1), MX = tree.Max_Query(1, 1, n, 1, indx - 1);
int cnt = mtree.Query(1, 1, n, 1, indx - 1, mn, mx);
if(mn > MX || MN > mx || cnt == 0)res = min(res, rec(i + 1) + 1);
else break;
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
v.resize(n + 1);
tree.init(n);
mtree.init(n);
for(int i = 1;i <= n;++i){
cin >> v[i];
}
tree.Build(1, 1, n, v);
mtree.Build(1, 1, n, v);
int res = 1e9;
for(int i = 1;i <= n;++i){
if(v[i] < v[i - 1])break;
res = min(res, rec(i + 1) + 1);
}
cout << res;
}
Compilation message
money.cpp: In member function 'std::vector<int> MergeSortTree::Merge(std::vector<int>&, std::vector<int>&)':
money.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(p1 < left.size() || p2 < right.size()){
| ~~~^~~~~~~~~~~~~
money.cpp:50:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(p1 < left.size() || p2 < right.size()){
| ~~~^~~~~~~~~~~~~~
money.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(p1 == left.size()){
| ~~~^~~~~~~~~~~~~~
money.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | else if(p2 == right.size()){
| ~~~^~~~~~~~~~~~~~~
money.cpp: In member function 'int MergeSortTree::Query(int, int, int, int, int, int, int)':
money.cpp:84:42: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type)'
84 | return max(0, itr2 - itr1 + 1);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from money.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
money.cpp:84:42: note: deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
84 | return max(0, itr2 - itr1 + 1);
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from money.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
money.cpp:84:42: note: deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'})
84 | return max(0, itr2 - itr1 + 1);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from money.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
money.cpp:84:42: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
84 | return max(0, itr2 - itr1 + 1);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from money.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
money.cpp:84:42: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
84 | return max(0, itr2 - itr1 + 1);
| ^
money.cpp:82:17: warning: unused variable 'pos1' [-Wunused-variable]
82 | int pos1 = itr1 - mTree[node].begin();
| ^~~~
money.cpp:83:17: warning: unused variable 'pos2' [-Wunused-variable]
83 | int pos2 = itr2 - mTree[node].begin();
| ^~~~
