PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Hazem Tarek
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2753
PREREQUISITES:
Segment Tree, Sweep Line
PROBLEM:
Let f([x_1,\,x_2,\,\cdots,\,x_k]) be the minimum number of subarrays such that each x_i belongs to exactly one subarray, and it’s possible to arrange the subarrays in a way that makes x increasing. For example, f([5,\,4,\,1,\,2,\,3]) = 3 since we can divide x into three subarrays: [5],\,[4],\,[1,\,2,\,3] then rearrange them to [1,\,2,\,3],\,[4],\,[5].
You are given a permutation P of length N. You are also given Q queries of the form L,\,R. For each query, find the value of f([P_L,\,P_{L+1},\,\cdots,\,P_R]).
EXPLANATION:
For each query [L, R], observe the following:
- In the optimal division, we only separate two consecutive elements into two subarrays if they are not consecutive values. For example, in f([1, 3, 2]), the optimal division is [1], [3], [2], and we separate 1 and 3 because they are not consecutive values (there is 2 in between). We call such pair of consecutive elements bad.
- Calculating f([P_L, P_L + 1, \dots, P_R]) is equivalent to counting the number of bad pairs in that range, since we only separate into a new subarray at each bad pair.
Therefore, the problem now turns into calculating the number of bad pairs in each query (inversely, counting the number of good pairs). This is still difficult to do directly, but notice the following:
- Suppose for some i such that P_i < P_{i + 1}, we calculate U_i < i to be the largest index such that P_i < P_{U_i} < P_{i + 1}, and V_i > i + 1 to be the smallest index such that P_i < P_{V_i} < P_{i + 1}. Then for any query L, R, (P_i, P_{i + 1}) is a good pair if and only if U_i < L \le i and i + 1 \le R < V_i. This is because any query with L \le U_i will include U_i in its subarray, and therefore make the pair bad; similar things can be said about queries with R \ge V_i.
We can find U_i and V_i for all pairs using segment tree (details is left as exercise for readers). Having all these information, the problem becomes counting the number of indices i such that the rectangle [U_i + 1, i] \times [i + 1, V_i - 1] covers the point (L, R). This is a classic problem that can be solved using sweep line and segment tree.
TIME COMPLEXITY:
Time complexity is O((N + Q) \log N) per test case.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e6+5;
int n,q;
int a[N],b[N];
int l[N],r[N];
int mx[N];
void build(int id,int l,int r){
mx[id]=0;
if(l==r) return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void upd(int id,int l,int r,int p,int x){
if(l==r){
mx[id]=x;return;
}
int mid=(l+r)/2;
if(p<=mid) upd(id*2,l,mid,p,x);
else upd(id*2+1,mid+1,r,p,x);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int qry(int id,int l,int r,int ql,int qr){
if(l>qr || r<ql) return 0;
if(ql<=l && r<=qr) return mx[id];
int mid=(l+r)/2;
return max(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
vector<pair<int,int> >qr[N];
vector<pair<int,int> >mf[N];
int ans[N],len[N];
int bit[N];
void bupd(int id,int v){
for(int i=id; i<=n ;i+=i&-i) bit[i]+=v;
}
int bqry(int id){
int res=0;
for(int i=id; i>=1 ;i-=i&-i) res+=bit[i];
return res;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> q;
for(int i=1; i<=n ;i++){
cin >> a[i];b[i]=a[i];
}
for(int i=1; i<n ;i++){
if(a[i]<a[i+1]) l[i]=qry(1,1,n,a[i],a[i+1])+1;
upd(1,1,n,a[i],i);
}
build(1,1,n);
for(int i=n; i>=2 ;i--){
if(a[i]>a[i-1]) r[i-1]=n-qry(1,1,n,a[i-1],a[i]);
upd(1,1,n,a[i],n-i+1);
}
for(int i=1; i<n ;i++){
if(a[i]<a[i+1]){
//cout << "!! " << l[i] << ' ' << r[i] << endl;
mf[i+1].push_back({l[i],1});
mf[i+1].push_back({i+1,-1});
mf[r[i]+1].push_back({l[i],-1});
mf[r[i]+1].push_back({i+1,1});
}
}
for(int i=1; i<=q ;i++){
int cl,cr;cin >> cl >> cr;
len[i]=cr-cl+1;
qr[cr].push_back({cl,i});
}
for(int i=1; i<=n ;i++){
for(auto c:mf[i]) bupd(c.fi,c.se);
for(auto c:qr[i]){
ans[c.se]=bqry(c.fi);
}
}
for(int i=1; i<=q ;i++){
cout << len[i]-ans[i] << '\n';
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n ,q;
scanf("%d%d",&n,&q);
vector <int> a(n); //1-based permutation
for(int&i : a)
scanf("%d",&i);
vector <vector <array <int ,2>>> qs(n+2);
for(int l,r,i = 0; i < q; i++){
scanf("%d%d",&l,&r);
qs[r].push_back({l ,i});
}
int s = n+2;
vector <int> t(2*s+1);
function <int(int ,int)> mrg;
auto upd = [&](int p ,int v){
for(t[p+=s] = v; p > 1; p>>=1)
t[p>>1] = mrg(t[p] ,t[p^1]);
};
auto qry = [&](int l ,int r){
int q = t.back();
for (l+=s ,r+=s+1; l < r; l>>=1 ,r>>=1){
if(l&1) q = mrg(q ,t[l++]);
if(r&1) q = mrg(q ,t[--r]);
}
return q;
};
vector <int> lf(n) ,rt(n);
fill(t.begin() ,t.end() ,0);
mrg = [](int x ,int y){ return max(x ,y); };
for(int i = 0; i+1 < n; i++){
lf[i+1] = a[i] < a[i+1]? qry(a[i] ,a[i+1]) : i+1;
upd(a[i] ,i+1);
}
fill(t.begin() ,t.end() ,n+1);
mrg = [](int x ,int y){ return min(x ,y); };
for(int i = n-1; i > 0; i--){
rt[i] = a[i-1] < a[i]? qry(a[i-1] ,a[i]) : i+1;
upd(a[i] ,i+1);
}
vector <vector <array <int ,2>>> us(n+2);
for(int i = 1; i < n; i++){
us[rt[i]].push_back({lf[i] ,-1});
us[rt[i]].push_back({i ,+1});
us[i+1].push_back({lf[i] ,+1});
}
vector <int> ans(q);
fill(t.begin() ,t.end() ,0);
mrg = [](int x ,int y){ return x + y; };
for(int r = 1; r <= n; r++){
for(auto&[l ,v] : us[r])
upd(l ,qry(l ,l)+v);
for(auto&[l ,i] : qs[r])
ans[i] = qry(l ,r);
}
for(int&i : ans)
printf("%d\n",i+1);
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T, class bin_op>
struct segment_tree {
#define lc i * 2
#define rc i * 2 + 1
#define m (l + r) / 2
T e; // default value
bin_op op;
vector<T> tr;
segment_tree(int _n, T _e, bin_op _op) : e(_e), op(_op) {
tr = vector<T>(4 * _n + 5, e);
}
void update(int l, int r, int i, int u, T v) {
if (l == r) {
tr[i] = op(tr[i], v);
} else {
if (u <= m) {
update(l, m, lc, u, v);
} else {
update(m + 1, r, rc, u, v);
}
tr[i] = op(tr[lc], tr[rc]);
}
}
T query(int l, int r, int i, int L, int R) {
if (l > R || r < L || L > R) {
return e;
} else if (L <= l && r <= R) {
return tr[i];
} else {
return op(query(l, m, lc, L, R),
query(m + 1, r, rc, L, R));
}
}
#undef lc
#undef rc
#undef m
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> l(n), r(n);
segment_tree get_right(n, n, [](int u, int v) { return min(u, v); });
for (int i = n - 2; i >= 0; i--) {
r[i] = a[i] < a[i + 1] ? get_right.query(1, n, 1, a[i], a[i + 1]) : 0;
get_right.update(1, n, 1, a[i + 1], i + 1);
}
segment_tree get_left(n, -1, [](int u, int v) { return max(u, v); });
for (int i = 0; i < n - 1; i++) {
l[i] = a[i] < a[i + 1] ? get_left.query(1, n, 1, a[i], a[i + 1]) : n - 1;
get_left.update(1, n, 1, a[i], i);
}
vector<vector<pair<int, int>>> eve(n + 1), que(n + 1);
for (int i = 0; i < n - 1; i++) {
// left of query must be in (l[i], i]
// right of query must be in [i + 1, r[i])
// l[i] is in [-1, n - 1], r[i] is is [0, n]
// use segment tree as prefix sum
if (l[i] < i && i + 1 < r[i]) {
eve[l[i] + 1].push_back({i + 1, 1});
eve[l[i] + 1].push_back({r[i], -1});
eve[i + 1].push_back({i + 1, -1});
eve[i + 1].push_back({r[i], 1});
}
}
vector<int> ans(q);
for (int i = 0; i < q; i++) {
int l, r; cin >> l >> r; l--; r--;
ans[i] = r - l + 1;
que[l].push_back({r, i});
}
segment_tree rectangle(n, 0, plus<int>());
for (int i = 0; i <= n; i++) {
for (auto [r, val] : eve[i]) {
rectangle.update(0, n, 1, r, val);
}
for (auto [r, ind] : que[i]) {
ans[ind] -= rectangle.query(0, n, 1, 0, r);
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}