<p>You are given a 2D array of integers <code>envelopes</code> where <code>envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>]</code> represents the width and the height of an envelope.</p>

<p>One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope&#39;s width and height.</p>

<p>Return <em>the maximum number of envelopes you can Russian doll (i.e., put one inside the other)</em>.</p>

<p><strong>Note:</strong> You cannot rotate an envelope.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[5,4],[6,4],[6,7],[2,3]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The maximum number of envelopes you can Russian doll is <code>3</code> ([2,3] =&gt; [5,4] =&gt; [6,7]).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> envelopes = [[1,1],[1,1],[1,1]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= envelopes.length &lt;= 10<sup>5</sup></code></li>
	<li><code>envelopes[i].length == 2</code></li>
	<li><code>1 &lt;= w<sub>i</sub>, h<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>



#include <bits/stdc++.h>
using namespace std;

#define maxn 100010

#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second




class Solution {
public:
    pii P[maxn];

    int n;
    int dp[maxn];
    int ST[10*maxn+10];

    void upd (int N, int L, int R, int ind, int val){
        if (L>R or L>ind or ind>R) return;

        if (L==R){
            ST[N]= max(ST[N], val);
            return;
        }

        int mid= (L+R)/2;
        upd (2*N+1, L, mid, ind, val);
        upd (2*N+2, mid+1, R, ind, val);
        ST[N]= max(ST[2*N+1], ST[2*N+2]);
    }

    int query (int N, int L, int R, int S, int E){
        if (L>=S and R<=E) return ST[N];
        if (L>R or L>E or S>R) return 0;
        int mid= (L+R)/2;
        return max (query(2*N+1, L, mid, S, E), query(2*N+2, mid+1, R, S, E));
    }



    int maxEnvelopes(vector<vector<int>>& envelopes) {
        n= envelopes.size();
        for (int i=0; i<n; i++) P[i+1]= mp(envelopes[i][0], envelopes[i][1]);
        sort(P+1, P+n+1);    
        for (int i=0; i<10*maxn+10; i++) ST[i]=0;
        for (int i=1; i<=n; i++) dp[i]=0;
        dp[1]=1;
        int prev_point= 0;
        P[0].first= -100;
        for (int i=1; i<=n; i++){
            if (P[i].first>P[i-1].first){
                for (int k=prev_point+1; k<i; k++) {
                    if (k>0){
                    //    cout<<"update "<<k<<" "<<P[k].first<<" POSITION "<<P[k].second+1<<" VALUE "<<dp[k]<<endl;
                     upd(1, 1, maxn, P[k].second+1, dp[k]);
                    }
                }
                    prev_point= i-1;
            }
            dp[i]= 1+query(1, 1, maxn, 1, P[i].second);
      //      cout<<"query "<<i<<" "<<P[i].first<<" POSITION "<<P[i].second<<" :: "<<dp[i]-1<<endl;


        } 
        int ans=0;

        for (int i=1; i<=n; i++) ans= max(ans, dp[i]);
        return ans;    
    }
};

87778