#include<bits/stdc++.h>
using namespace std;
#define int long long
/*
so notice that if the sequence is like 1,2,3,4,5 then the answer is just 5, because we take [1,2,3,4,5] then [2,3,4,5],...
in fact even if it was 1,2,3,4,6 or 1,2,4,5,6 the answer remains the same. because the exact number doesn't matter, it only
matters that we have an increasing (or rather, non decreasing) sequence.
now what if there is a decrease? then it's 1,2,3,2 for example. then, the answer:
[1,2,3,2]->[0,1,2,1]->[0,0,1,0]->[0,0,0,0]. so answer is 3 because 1+1+1. wait, why is it 3? oh, because there was 2 increases and
1 decrease. wait, but for the first example, there are 4 increases. why is the answer 5? let me check: 1,2,3,4,5->0,1,2,3,4->
0,0,1,2,3->0,0,0,1,2->0,0,0,0,1->0,0,0,0,0. yeah, it's 5.
what if [3,4,3,2]? then 3,4,3,2->1,2,1,0->0,1,0,0->0,0,0,0. answer is 3. because we increase once and decrease twice. wait,
but count is not all we need to keep track of, right? [3,5,4,2]: 3,5,4,2->1,3,2,0->0,2,1,0->0,1,0,0->0,0,0,0. answer: 4.
why is there a difference? because 4-3=1 so we need to spend 1 more op dealing with the thing.
oh, difference array?
difference array of [3,4,3,2]: [1,-1,-1] -> 1 increase only. answer is 3
difference array of [3,5,4,2]: [2,-1,-2] -> 2 decreases. answer is 4
wait, i don't see the pattern. let's look at sample TCs
[2,2,2]-> difference array is all 0. answer is 1
[2,3,3,3,2] -> [1,0,0,-1]. answer is 2
[1,2,3,2,1,3] -> [1,1,-1,-1,2]. answer is 4
no pattern yet. let's see, if the element decreases from i to i+1 (ie. difference array is negative), like 2->1, then we need to
get i+1 first. then we can get i.
let's start over.
increasing groups.
[3,5,4,2]: separate into groups of increasing elements. so [3,5], [4], [2].
[3,4,3,2]: [3,4],[3],[2]. wait, but answer is 3. oh, maybe it looks like [3,4,3],[2]. because as long as it's not less than 3
we can take them. but that makes no sense, what do we do with the 4? it will become a 1.
oh, maybe EITHER an increasing or decreasing subsequence works.
[3,4], [3,2].
[3,5], [4,2]. wait. that doesn't work.
what if dnc dp? every time we pivot on the smallest element. then split into 2. so, [3,5,4],[2] -> [3],[5,4]. -> [5],[4] -> ans = 4
then [3,4,3,2]->[3,4,3],[2]->[4]. wait so what if there are multiple elements w same value? we need to split into a lot of groups.
oh, what about for every element we find 1) the next occurrence of it, and 2) the next occurrence of any number smaller than it.
then, say [3,5,4,2]. 3->2, 5->4, 4->2.
observation!
if all the elements are unique then the answer will be N. very intuitive.
so the only problem is when there are repeated elements. so we can just stop considering [3,5,4,2], lets go to [3,4,3,2].
after index 1, next occurrence of 3 is index 3. in between them there is a 4, meaning we need to increase answer by 1 (for the 3s)
+ 1 (for the 4). notice that this works because the 4 is bigger. what if it was [3,2,3]? then answer is 3 because we must reduce the
2 first -> [1,0,1]->+2. so let the next occurrence of the number smaller than it be bi, and repeated next occurrence be ai.
then if bi > ai then it's all good, we just mark ai as done, then for the numbers in between we process normally.
but what if bi < ai ? then we need to increase answer by 2 + 1 = 3, and also mark ai as done, and mark bi as done too.
does that work?
check sample test case
2,2,2. there is no bi, and there is ai, wait our algo gives answer 2.
oh we can use a while loop! while
oh wait, ufds?? we can merge elements if they are greater, and ans++. if same, then ignore. but if we meet smaller element, then have to restart the set and ans++.
wait, no need to ufds lol.
*/
using ll = long long;
vector<ll> seg;
void update(int idx, int l, int r, int pos, ll val) {
if(l == r) {
seg[idx] = val;
return;
}
int mid = (l + r) / 2;
if(pos <= mid)
update(idx*2, l, mid, pos, val);
else
update(idx*2+1, mid+1, r, pos, val);
seg[idx] = min(seg[idx*2], seg[idx*2+1]);
}
// Find the smallest index in [l, r] whose stored value is <= b.
// Returns -1 if none exists.
int query_first(int idx, int l, int r, ll b) {
if(seg[idx] > b) return -1;
if(l == r) return l;
int mid = (l + r) / 2;
if(seg[idx*2] < b)
return query_first(idx*2, l, mid, b);
else
return query_first(idx*2+1, mid+1, r, b);
}
signed main() {
int n; cin >> n;
vector<int> a(n), b(n, -1);
seg.resize(4*n, 1e12);
map<int, int> last_occur;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (last_occur.count(a[i])) {
b[last_occur[a[i]]] = i;
}
last_occur[a[i]] = i;
update(1, 1, n, i, a[i]);
}
int ans = n;
for (int i = 0; i < n; i++) {
int x = a[i];
int next_occur = b[i];
int next_smaller = query_first(1, i+1, n, x);
// cout << next_occur << " " << next_smaller << endl;
if (next_occur != -1 && (next_smaller == -1 || next_smaller > next_occur)) {
// we're actually subtracting the contribution by the next occurrence
ans--;
}
}
cout << ans << endl;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
