# First time use segment tree to AC a problem in ABC

Segment tree is powerful, however, I never fully understand the code. The good part is we have many nice template online. Today in the problem E of the ABC 339 contest, the segment tree can be used to solve this problem.

This is the first time I am using segment tree to AC to problem in contest. Cheers! Thank for the code from this link.

# Problem

E — Smooth Subsequence

# Basic idea:

when have a new num, we check:

• the max res from [L, R] where L = num- d, R = num + d
• then the current_result will be max_result + 1
• update this max_result

Above operation can use segment tree to solve with time complexity of O(n log n), which is enough for this problem.

# Code in C++

`#include<stdio.h>                                                                       #include<string.h>                                                                      #include<iostream>                                                                      #include<algorithm>                                                                     #include<vector>                                                                        using namespace std;                                                                    #define ll long long                                                                    const int MAX_LEN =1000000;                                                             int seg_tree[MAX_LEN << 2];                                                             int Lazy[MAX_LEN << 2];                                                                 int arr[MAX_LEN];                                                                       //从下往上更新 节点                                                                     void push_up (int root) {                                                                   seg_tree[root] = max(seg_tree[root << 1], seg_tree[root << 1 | 1]);      //最小值改min}                                                                                       //从上向下更新，左右孩子                                                                void push_down (int root, int L, int R) {                                                   if(Lazy[root]){                                                                             Lazy[root << 1] += Lazy [root];                                                         Lazy[root << 1 | 1] += Lazy[root];                                                      int mid = (L + R) >> 1;                                                                 seg_tree[root << 1] +=  Lazy[root] * (mid - L + 1);                                     seg_tree[root << 1 | 1] += Lazy[root] * (R - mid);                                      Lazy[root] = 0;                                                                     }                                                                                   }                                                                                       //建树                                                                                  //[L,R]就是对应arr数组里面的数                                                          void build (int root, int L, int R) {                                                       Lazy[root] = 0;                                                                         if(L == R) {                                                                                seg_tree[root] = arr[L];                                                                return ;                                                                            }                                                                                       int mid = (L + R) >> 1;                                                                 build(root << 1, L, mid);                                                               build(root << 1 | 1, mid + 1, R);                                                       push_up(root);                                                                      }                                                                                                                                                                               //区间查询                                                                              //查找区间[LL,RR]的最大/小值                                                            int query (int root, int L, int R, int LL, int RR) {                                        if (LL <= L && R <= RR) return seg_tree[root];                                          push_down(root, L, R);     //每次访问都去检查Lazy 标记                                  int Ans = 0;                                                                            int mid = (L + R) >> 1;                                                                 if(LL <= mid) Ans = max(Ans, query(root << 1, L, mid, LL, RR));    //最小值改min        if(RR > mid) Ans = max(Ans, query(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min    return Ans;                                                                         }                                                                                       //区间修改 +-某值                                                                       //使得区间[LL,RR]的值都加上val                                                          void update_Interval(int root, int L, int R, int LL, int RR, int val){                      if (LL <= L && R <= RR) {                                                                   Lazy[root] += val;                                                                      seg_tree[root] += val * (R - L + 1);                                                    return ;                                                                            }                                                                                       push_down(root, L, R);                                                                  int mid = (L + R) >> 1;                                                                 if (LL <= mid) update_Interval(root << 1, L, mid, LL, RR, val);                         if (RR > mid) update_Interval(root << 1 | 1, mid + 1, R, LL , RR, val);                 push_up(root);                                                                      }                                                                                       //单点修改 可以改为某值，或者+-某值                                                     //把pos位置的值改成val                                                                  void update(int root, int L, int R, int pos, int val) {                                     if(L == R){                                                                                 seg_tree[root] = val;    //点直接变为某值                                               return ;                                                                            }                                                                                       int mid = (L + R) >> 1;                                                                 if(pos <= mid) update(root << 1, L, mid, pos, val);                                     else update(root << 1 | 1, mid + 1, R, pos, val);                                       push_up(root);                                                                      }                                                                                       int main()                                                                              {                                                                                           int n,d;                                                                                scanf("%d%d",&n,&d);                                                                    vector<int> nums(n+100, 0);                                                             int D = 1;                                                                              for(int i=1;i<=n;++i)                                                                   {                                                                                           scanf("%d",&nums[i]);                                                                   D = max(nums[i], D);                                                                    arr[i] = 0;                                                                         }                                                                                       //cout << D << endl;                                                                    build(1,1,D+100);                                                                       //cout << D << endl;                                                                    int ret = 0;                                                                                                                                                                    for (int i = 1; i <=n; ++i)                                                             {                                                                                           int num = nums[i];                                                                      int l = max(1, num - d);                                                                int r = min(D, num + d);                                                                //cout << i <<" "<< nums[i] <<" "<< ret << " l "<<l <<" --r "<<r<< endl;                int this_ret = query(1,1,D,l,r) + 1;                                                    ret = max(ret, this_ret);                                                               //cout << i <<" "<< nums[i] <<" "<< this_ret << " l "<<l <<"r "<<r<< endl;              update(1, 1, D, num, this_ret);                                                     }                                                                                       cout << ret << endl;                                                                    return 0;                                                                           }     `

--

--