PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Mradul Bhatnagar
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Two Pointers, Binary Search
PROBLEM:
You are given an array A of length N.
Let F(L,R) be the array you get from A after removing all occurrences of A_L, A_{L+1}, \dots , A_R. In other words, for each value in A between the indices L and R, you delete every occurrence of that value, including occurrences outside the range [L, R].
A pair (L, R) is called good if 1\le L\le R\le N and F(L, R) is sorted in non-decreasing order. In the case that F(L, R) is the empty array, we say it is sorted.
Count the number of good pairs.
EXPLANATAION:
F(L, R) denotes the subarray whose starting index is L and ending index is R.
Claim: If there exists a subarray A[L, R] which is good then all the subarrays whose starting index is L and the ending index greater than R will also be good subarrays.
Why
If the subarray A[L, R] is good that means removing all the occurrences of all the elements of this subarray from the array A will make the resultant array sorted in non-decreasing order.
Now consider any subarray whose ending index is greater than R and starting index is L then:
The subarray A[L, R] is still part of the new subarray. So deleting all the occurrences of all the elements of the subarray A[L, R] from array A will make the array sorted. Now if we delete any element from the sorted array, the array will remain sorted. How?
Consider any array A such that the array is sorted in non-decreasing order:
Let us delete any element from the array say A_3. After deletion of element A_3, the elements A_2 and A_4 of the array becomes adjacent to each other. Since A_4>A_3 and A_3>A_2, it means that A_4>A_2. Hence our resultant array will be:
which remains sorted.
Hence all the subarray whose ending index is greater than R and starting index is L will be good as they contain the subarray A[L, R] which is sufficient to make the array sorted,
Hence for every index i of an array A we will consider that as the starting index of the subarray and will try to find the minimum ending index e such that the subarray A[i,e] is good.
If we try to find the minimum ending index for every possible starting index naively it will be O(N^2) which is quite slow to pass the constraints. Can we optimize it further?
Claim: If the minimum ending index for i is e, then the ending index of j will be greater than or equal to e such that j>i.
Proof
We will try to prove it by contradiction:
Suppose for index i the minimum ending index is e such that subarray A[i, e] is good. Now we say that for the index i+1, the minimum ending index is e-1. It means that the subarray A[i+1,e-1] is sufficient to make the resultant array sorted in the non-decreasing order.
As the subarray A[i+1,e-1] is part of the subarray A[i,e] which means for the subarray A[i,e] removing all the occurrences of all the elements of A[i+1,e-1] is sufficient to make the array sorted. Hence the minimum ending index for the subarray which starts from index i is e-1 which contadicts our assumption.
Hence If the minimum ending index for i is e, then the ending index of j will be greater than or equal to e such that j>i.
So, we can use the two-pointers approach to find the minimum ending index e for every index i of an array A. Once we know the minimum ending index e for every index i, it’s quite easy to find the total number of the good subarrays.
Rest is the implementation. One of the ways to implement is:
Spoiler
Suppose there are only two numbers x and y in the array such that x<y. If the last occurrence of x is greater than the first occurrence of y in an array, then the array won’t be sorted. Now removing all the occurrence of either x or y will make the array sorted in non-decreasing order.
What if the array contains more than 2 elements. Do we need to compare an element with all the elements of the array? No !! It’s enough to compare it with the next smaller (or next greater) element of the array if it exists. Try to prove why? Hence we will store the count of elements that creates trouble in an array.
Now, let us try to find the minimum ending index e for the subarray with starts at index 1. Initially, our ending index is at position 1, we will keep on deleting all the occurrences of elements present at index e and increment e until there is no trouble in an array. Let x be the deleted index, y and z the next smaller and next greater element of x.
- Trouble reduces by 1 if the last occurrence of y is larger than the first occurrence of x.
- Trouble reduces by 1 if the last occurrence of x is larger than the first occurrence of z
- Trouble increases by 1 if the last occurrence of y is larger than the first occurrence of z since now y and z are adjacents.
We can easily find the next smaller and next larger element of x by performing a binary search.
As soon as our trouble becomes 0, that is the minimum ending index e for index i.
Once all the minimum ending indexes are found for every starting index, we are done.
TIME COMPLEXITY:
O(N*log(N) per test case
SOLUTIONS:
Setter
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int T = 10'000, N = 200'000;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
assert(te <= T);
int sumn = 0;
while(te--) {
int n;
cin >> n;
sumn += n;
assert(sumn <= N);
vi a(n);
map<int, int> ma, le, ri;
rep(i, 0, n) {
cin >> a[i];
ma[a[i]]++;
if(!le.count(a[i])) le[a[i]] = i;
ri[a[i]] = i;
}
ll ans = 0;
int j = 0;
int cnt = 0;
auto conflict = [&] (int x, int y) {
assert(x < y);
return ri[x] > le[y];
};
map<int, int> ma2;
set<int> se;
auto add = [&](int x) {
auto it = se.lower_bound(x);
if(it != se.end() && it != se.begin()) {
cnt -= conflict(*prev(it), *it);
}
if(it != se.end()) {
assert(x != *it);
cnt += conflict(x, *it);
}
if(it != se.begin()) cnt += conflict(*prev(it), x);
se.insert(it, x);
};
auto del = [&](int x) {
auto it = se.find(x);
assert(it != se.end());
if(next(it) != se.end()) cnt -= conflict(x, *next(it));
if(it != se.begin()) cnt -= conflict(*prev(it), x);
if(next(it) != se.end() && it != se.begin()) cnt += conflict(*prev(it), *next(it));
se.erase(x);
};
for(auto &pa : ma) add(pa.first);
rep(i, 0, n) {
while(j == i || (j < n && cnt > 0)) {
// add a[j]
if(ma2[a[j]] == 0) del(a[j]);
ma2[a[j]]++;
j++;
}
if(cnt == 0) ans += n - j + 1;
// erase a[i]
ma2[a[i]]--;
if(ma2[a[i]] == 0) add(a[i]);
}
cout << ans << '\n';
}
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
set <int> s1;
map<int,int> le,ri,co;
int prob;
#define int long long
void remove(int x)
{
if(co[x]==0)
{
auto itr=s1.lower_bound(x);
s1.erase(x);
int l=-1,r=-1;
itr=s1.lower_bound(x);
if(itr!=s1.end())
r=*itr;
if(itr!=s1.begin())
{
itr--;
l=*itr;
}
if(l!=-1 && ri[l]>le[x])
prob-=1;
if(r!=-1 && ri[x]>le[r])
prob-=1;
if(l!=-1 && r!=-1 && ri[l]>le[r])
prob+=1;
}
co[x]++;
}
void add(int x)
{
co[x]--;
if(co[x]==0)
{
auto itr=s1.lower_bound(x);
int l=-1,r=-1;
if(itr!=s1.end())
r=*itr;
if(itr!=s1.begin())
{
itr--;
l=*itr;
}
if(l!=-1 && ri[l]>le[x])
prob+=1;
if(r!=-1 && ri[x]>le[r])
prob+=1;
if(l!=-1 && r!=-1 && ri[l]>le[r])
prob-=1;
s1.insert(x);
}
}
void solve()
{
int n;
cin>>n;
int a[n];
s1.clear();
le.clear();
ri.clear();
co.clear();
for(int i=0;i<n;i++)
{
cin>>a[i];
s1.insert(a[i]);
if(!le.count(a[i]))
le[a[i]]=i;
ri[a[i]]=i;
}
int ans=0;
prob=0;
for(auto itr=s1.begin();itr!=s1.end();itr++)
{
if(itr!=s1.begin())
{
auto ptr=--itr;
itr++;
if(ri[*ptr]>le[*itr])
prob++;
}
}
if(prob==0)
{
int temp=n*(n+1);
temp/=2;
cout<<temp<<"\n";
return;
}
int l=0,r=0;
for(int l=0;l<n;l++)
{
while(prob>0 && r<n)
{
remove(a[r]);
r++;
}
if(prob==0)
ans+=(n+1-r);
add(a[l]);
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
