First time use segment tree to AC a problem in ABC
3 min readFeb 3, 2024
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
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;
} 