Can anyone tell me how this problem can be solved using binary search. And if someone has solved it can he share his or her code as well
maybe this could help you. It’s a good problem but I don’t think that such constraints are okay for a Classical problem.
@hello_hell Actually I had read it but still I was finding it difficult to count no. Of LIS
But Still Thanks for your time and help
Let dp_i denote the number of increasing sequences ending at A_i. Let L_i denote the length of the LIS from 1 to i. L_i = max(L_j + 1) for all j such that A_j < A_i. Now dp_i = \sum_{L_j + 1 = L_i\ \&\ A_j < A_i}dp_j.
To implement this, we can notice that we only need relative values, so we remap the array A to smaller values. As we can see, we need the largest L calculated until now from 0 to A_i, and the sum of their respective dp values. Remeber as values can be repeated, when updating values, remember to add and not assign. We want a segment tree where the ith element consists of the largest sequence ending at a value of i and how many such sequences exist. Now when we want to merge 2 nodes i and j, check if L_i = L_j. If it is not, return the node with larger L. Otherwise return L_i and dp_i + dp_j, since we can then get LIS from both.
Implementation
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const int p = 1e9 + 7;
struct segment_tree{
vector<pair<int,int>> segtree;
pair<int,int> join(const pair<int,int> &x, const pair<int,int> &y){
if(x.first > y.first){
return x;
}
if(x.first < y.first){
return y;
}
return mp(x.first/*== y.first*/ , (x.second + y.second)%p);
}
int n;
segment_tree(int n) : n(n){
segtree.resize(n<<1, {0,0});
}
void update(int pos, pair<int,int> val){
pos+=n;
segtree[pos]=join(val, segtree[pos]);
pos>>=1;
while(pos){
segtree[pos]=join(segtree[pos<<1],segtree[(pos<<1)|1]);
pos>>=1;
}
}
pair<int,int> query(int x, int y){
x+=n;
y+=n+1;
pair<int,int> ans = {0,0};
while(x<y){
if(x&1){
ans=join(ans, segtree[x++]);
}
if(y&1){
ans=join(segtree[--y], ans);
}
x>>=1;
y>>=1;
}
return ans;
}
};
void solve(){
int n;
cin>>n;
vector<int> seq(n);
for(auto &x : seq){
cin>>x;
}
vector<int> mapper(seq.begin(), seq.end());
sort(mapper.begin(), mapper.end());
mapper.resize(unique(mapper.begin(), mapper.end()) - mapper.begin());
for(auto &x : seq){
x = lower_bound(mapper.begin(), mapper.end(), x) - mapper.begin() + 1;
}
segment_tree segtree(mapper.size() + 1);
segtree.update(0, {0,1});
for(const auto &x : seq){
auto curr = segtree.query(0, x-1);
segtree.update(x, {curr.first+1, curr.second});
}
auto ans = segtree.query(0, mapper.size());
cout<<ans.first<<" "<<ans.second<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
1 Like