- Advanced Data Structure, Dynamic Programming, LIS, Segment-Tree, Tree, TrueGeek-2021

Length of Longest Increasing Subsequences (LIS) using Segment Tree

#include using namespace std;  #define M 100000  vector tree(4 * M + 1);  void update_tree(int start, int end,                 int update_idx, int length_t,                 int count_c, int idx){            if (start == end        && start == update_idx) {        tree[idx].first            = max(tree[idx].first, length_t);        tree[idx].second = count_c;        return;    }          if (update_idx < start        || end < update_idx) {        return;    }          int mid = (start + end) / 2;      update_tree(start, mid, update_idx,                length_t, count_c,                2 * idx);    update_tree(mid + 1, end, update_idx,                length_t, count_c,                2 * idx + 1);              if (tree[2 * idx].first        == tree[2 * idx + 1].first) {        tree[idx].first            = tree[2 * idx].first;        tree[idx].second            = tree[2 * idx].second              + tree[2 * idx + 1].second;    }          else if (tree[2 * idx].first             > tree[2 * idx + 1].first) {        tree[idx] = tree[2 * idx];    }          else {        tree[idx] = tree[2 * idx + 1];    }}  pair query(int start, int end,                     int query_start,                     int query_end, int idx){            if (query_start left_child.first) {        return right_child;    }                  return make_pair(left_child.first,                     left_child.second                         + right_child.second);}  bool comp(pair a, pair b){    if (a.first == b.first) {        return a.second > b.second;    }    return a.first < b.first;}  int countLIS(int arr[], int n){        vector pair_array(n);    for (int i = 0; i < n; i++) {        pair_array[i].first = arr[i];        pair_array[i].second = i;    }              sort(pair_array.begin(),         pair_array.end(), comp);              for (int i = 0; i < n; i++) {          int update_idx = pair_array[i].second;                  if (update_idx == 0) {            update_tree(0, n - 1, 0, 1, 1, 1);            continue;        }                  pair temp            = query(0, n - 1, 0,                    update_idx - 1, 1);                  update_tree(0, n - 1, update_idx,                    temp.first + 1,                    max(1, temp.second), 1);    }          pair ans        = query(0, n - 1, 0, n - 1, 1);          return ans.second;}  int main(){    int arr[] = { 1, 3, 5, 4, 7 };    int n = sizeof(arr) / sizeof(int);      cout