Given n integers x 1 ,x 2 ,...,x n . Delete from them the least number of integers…
- User
Given n integers x 1 ,x 2 ,...,x n . Delete from them the least number of integers so that the rest were in ascending order.
Input The first line contains the number n (1≤n≤10 5 ). The second line contains the integers x 1 ,x 2 ,...,x n (1≤x i ≤60000).
Output Print in the first line the number of not erased integers. In the second line print the list of unerased integers in the original order. If several answers exist, print any.
Examples Input #1 6 2 5 3 4 6 1 Answer #1 4 2 3 4 6 Submissions 4K Acceptance rate 24% Bu sualda #include <bits/stdc++.h>
using namespace std;
#define ll long long #define ld long double #define endl '\n' #define pb push_back #define speedyboy ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(x) x.begin() , x.end() #define F first #define S second #define pll pair<ll , ll> #define pss pair<string , string> #define YES cout << "YES" << endl; #define NO cout << "NO" << endl;
const ll sz = 5e5 + 5 , INF = 1e9 , MOD = 998244353; ll a[sz] , m[sz] , idx[sz];
ll i , j , k; void solve(){ ll n; cin >> n; for(i = 1 ; i <= n ; i++){ cin >> a[i]; } ll say = 0; for(i = 1 ; i <= n ; i++){ ll it = lower_bound(m , m + say , a[i]) - m; m[it] = a[i]; idx[it] = i; if(it == say){ say++; } } cout << say << endl; }
signed main(){ speedyboy; ll t = 1; //cin >> t; while(t--){ solve(); } } Kodumu davam elətdir
- Assistant
Sure, let's continue and complete your code to not only find the length of the Longest Increasing Subsequence (LIS) but also reconstruct and print the actual subsequence.
Understanding the Current Code
Your current implementation efficiently computes the length of the LIS using a dynamic programming approach with binary search, achieving an ( O(n \log n) ) time complexity. Here's a brief overview:
-
Arrays Used:
a[]: Stores the input sequence.m[]: Maintains the smallest possible tail for all increasing subsequences of various lengths.idx[]: Keeps track of the indices ina[]corresponding to the elements inm[].
-
Variables:
say: Represents the current length of the LIS.
-
Logic:
- For each element in
a[], find its position (it) inm[]usinglower_bound. - Update
m[it]andidx[it]accordingly. - If a new element extends the LIS (
it == say), incrementsay.
- For each element in
Extending the Code to Reconstruct the LIS
To reconstruct the actual LIS, we need to keep track of the predecessors for each element in the potential subsequences. Here's how you can do it:
-
Introduce a
predecessor[]Array:- This array will store the index of the previous element in the LIS for each element in
a[].
- This array will store the index of the previous element in the LIS for each element in
-
Modify the Loop to Populate
predecessor[]:- When you place a new element in
m[it], set its predecessor to the index of the last element of the subsequence of lengthit - 1.
- When you place a new element in
-
Reconstruct the LIS:
- Starting from the last index of the LIS, backtrack using the
predecessor[]array to collect all elements of the LIS.
- Starting from the last index of the LIS, backtrack using the
Complete Code Implementation
Here's the complete code with the necessary modifications and explanations:
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define speedyboy ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); const ll sz = 1e5 + 5; // Adjusted size based on constraints ll a[sz], m[sz], idx_m[sz]; ll predecessor_idx[sz]; void solve(){ ll n; cin >> n; for(ll i = 1; i <= n; i++){ cin >> a[i]; } // Initialize ll length = 0; // Initialize m and idx_m with 0, not strictly necessary as we'll overwrite them // Initialize predecessor indices to -1 for(ll i = 0; i <= n; i++) { predecessor_idx[i] = -1; } for(ll i = 1; i <= n; i++){ // Find the insertion point for a[i] in m[1..length] ll pos = lower_bound(m + 1, m + length + 1, a[i]) - m; // Update m and idx_m m[pos] = a[i]; idx_m[pos] = i; // Set the predecessor index if(pos > 1){ predecessor_idx[i] = idx_m[pos - 1]; } // If a new LIS length is found, increment the length if(pos > length){ length = pos; } } // Reconstruct the LIS vector<ll> lis_indices(length); ll k = idx_m[length]; lis_indices[length - 1] = k; for(ll i = length - 2; i >= 0; i--){ k = predecessor_idx[k]; lis_indices[i] = k; } // Output cout << length << endl; for(ll i = 0; i < length; i++){ cout << a[lis_indices[i]] << " "; } cout << endl; } int main(){ speedyboy; ll t = 1; // If multiple test cases are expected, uncomment the next line // cin >> t; while(t--){ solve(); } }Explanation of the Added Parts
-
predecessor_idx[]Array:- Purpose: To store the index of the previous element in the LIS for each element.
- Initialization: Set all elements to
-1to denote the start of a subsequence.
-
Updating
predecessor_idx:- When an element
a[i]is placed at positionposinm[]:- If
pos > 1, it means there's a previous element in the subsequence. Setpredecessor_idx[i] = idx_m[pos - 1]. - If
pos == 1,a[i]is the start of a subsequence, so its predecessor remains-1.
- If
- When an element
-
Reconstructing the LIS:
- Start from the last element of the LIS, which is at index
idx_m[length]. - Use the
predecessor_idx[]array to backtrack and collect all elements of the LIS. - Store the indices of the LIS in
lis_indices[]and then print the corresponding values froma[].
- Start from the last element of the LIS, which is at index
Example Walkthrough
Let's walk through the provided example to see how the code works:
Input:
6 2 5 3 4 6 1Processing:
-
Step 1: i=1, a[i]=2
- pos=1
- m[1]=2, idx_m[1]=1
- predecessor_idx[1]=-1
- length=1
-
Step 2: i=2, a[i]=5
- pos=2
- m[2]=5, idx_m[2]=2
- predecessor_idx[2]=1
- length=2
-
Step 3: i=3, a[i]=3
- pos=2
- m[2]=3, idx_m[2]=3
- predecessor_idx[3]=1
- length=2
-
Step 4: i=4, a[i]=4
- pos=3
- m[3]=4, idx_m[3]=4
- predecessor_idx[4]=3
- length=3
-
Step 5: i=5, a[i]=6
- pos=4
- m[4]=6, idx_m[4]=5
- predecessor_idx[5]=4
- length=4
-
Step 6: i=6, a[i]=1
- pos=1
- m[1]=1, idx_m[1]=6
- predecessor_idx[6]=-1
- length=4
Reconstruction:
- Start from index 5 (a[5]=6)
- predecessor of 5 is 4
- predecessor of 4 is 3
- predecessor of 3 is 1
- predecessor of 1 is -1
LIS Indices: [1, 3, 4, 5]
LIS: [2, 3, 4, 6]
Output:
4 2 3 4 6Conclusion
With these additions, the code efficiently computes both the length of the LIS and reconstructs one such subsequence. This approach ensures that the subsequence is printed in the original order as required by the problem statement.
-