前提
看懂这篇题解，您需要：
1、线段树基本操作
2、不错的$dp$能力
3、$STL$ 入门函数
题目分析
首先，题目中的关键点就是这个式子：
$abs(x_i-x_j) ge$ $w_i+w_j$。
如果分别比较两个点间的距离和权值和，感觉是不可避免的$O(N^2)$枚举了（不排除是我太蒟了）那么，何不化简一下式子呢？
在保证$x_i ge x_j$的情况下，我们可以将不等式移项，变成$x_i - w_i ge x_j + w_j$
那么，怎么保证 $x_i$ 一定大于 $x_j$ 呢？ 不妨将$x$从小到大排序。
这样，当我们枚举到$x_i$的时候，就可以保证$x_j (j ∈ [1,i-1])$一定小于$x$。
其次，由于题目中对于点的选择看似“无序”， 用$dp$应该会比较容易处理。
设 $dp_i$ 表示在第 $i$ 个点，我们可以得到的最大团。 那么，状态转移方程就很好写了：
$dp_i = max{dp_j} + 1 $其中 $j ∈ [1,i)$， 且 $j$ 合法。
但是，这题真的就一个一维$dp$就可以过吗？ 在考虑如何判断$j$合法的时候，发现我们还是得要枚举$j$, 复杂度始终下不来。
如何不枚举$j$就能判断合法性呢？
对于 $x_i - w_i$，我们是可以$O(1)$计算的。
那么，我们为何不用$STL$中的 lower_bound函数呢？
将所有的$x_i + w_i$存入一个数组中，然后将其从小到大排序。那么，如果我们对他从小到大排序，只需要在这个数组中对 $x_i - w_i$进行lower_bound或者 upper_bound 查询，我们就可以知道$x_i - w_i$在数组中的位置，那么在这个位置之前的数就肯定都是合法的啦！
最后一个问题：如何快速查找区间的最大值呢？
这时候，我们不妨将$dp$的定义稍微进行一下修改： $dp_i$表示在第$i$大的$x_i + w_i$上，可以得到的最大团的大小。
这样做，我们就可以使得$dp$数组的下标连续起来，然后考虑用线段树优化$dp$,快速查询区间最大值，复杂度就可以降到$O(NlogN)$啦。
来一波代码：
#include <bits/stdc++.h> using namespace std; #define N 200010 #define ll long long template <class T> inline void read(T& a){ T x = 0, s = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); } a = x * s; return ; } struct hehe{ int maxn; } ; struct Segment_tree{ // 线段树板子 hehe e[N << 2]; inline void pushup(int o){ e[o].maxn = max(e[o << 1].maxn, e[o << 1 | 1].maxn); return ; } void update(int o, int l, int r, int x, int k){ if(l > x || r < x) return ; if(l == r && l == x){ e[o].maxn = k; return ; } int mid = l + r >> 1; update(o << 1, l, mid, x, k); update(o << 1 | 1, mid + 1, r, x, k); pushup(o); return ; } int query(int o, int l, int r, int in, int end){ if(l > end || r < in) return 0; if(l >= in && r <= end) return e[o].maxn; int mid = l + r >> 1; return max(query(o << 1, l, mid, in, end), query(o << 1 | 1, mid + 1, r, in, end)); } } tree; struct node{ int x, w; } t[N]; int temp[N]; int n, m; int dp[N]; bool cmp(node a, node b){ // 按照 x 排序 return a.x < b.x; } int main(){ // freopen("clique.in", "r", stdin); freopen("clique.out", "w", stdout); read(m); for(int i = 1; i <= m; i++){ read(t[i].x), read(t[i].w); temp[i] = t[i].x + t[i].w; } sort(temp + 1, temp + m + 1); sort(t + 1, t + m + 1, cmp); n = unique(temp + 1, temp + m + 1) - temp - 1; // 记得去重 for(int j = 1; j <= m; j++){ int pos = upper_bound(temp + 1, temp + n + 1, t[j].x - t[j].w) - temp - 1; // 第一个大于值的位置 int tmp = tree.query(1, 1, n, 1, pos); pos = lower_bound(temp + 1, temp + n + 1, t[j].x + t[j].w) - temp - 1; // 第一个大于等于当前值的位置 pos++; if(dp[pos] <= tmp + 1){ dp[pos] = tmp + 1; tree.update(1, 1, n, pos, tmp + 1); } } printf("%d ", tree.query(1, 1, n, 1, n)); return 0; }