题目链接：点击打开链接
题意：
给定数轴上的n个点。
下面n行每行两个数 xi, wi 表示点和点权。
对于任意两个点u, v
若dis(u,v) >= u_w+v_w 则这两个点间可以建一条边。(in other words 若两点间距离大于两点的权值和则可以建边）
找一个最大团，输出这个最大团的点数。
其实对于一个权值点我们可以认为是一个区间
如: 4 5 ,可以认为是区间[-1, 9]
则这个点可以从区间(-inf, 1]转移过来，，即val(9) = max(val(9), 区间(-inf, -1]最大值+1)
然后前面区间最值就用树状数组或者线段树维护
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <set> #include <vector>#include <string>#include <algorithm> template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int N = 400010;#define L(x) tree[x].l#define R(x) tree[x].r#define Max(x) tree[x].max#define Lson(x) (x<<1)#define Rson(x) (x<<1|1)#define Lazy(x) tree[x].lazystruct Node{int l, r, max, lazy;}tree[N<<2];void Down(int id){Max(Lson(id)) = max(Lazy(id), Max(Lson(id)));Max(Rson(id)) = max(Lazy(id), Max(Rson(id)));Lazy(Lson(id)) = max(Lazy(id), Lazy(Lson(id)));Lazy(Rson(id)) = max(Lazy(id), Lazy(Rson(id)));}void U(int id){Max(id) = max(Max(Lson(id)), Max(Rson(id)));}void build(int l, int r, int id){L(id) = l; R(id) = r;Max(id) = Lazy(id) = 0;if (l == r)return;int mid = (l + r) >> 1;build(l, mid, Lson(id)); build(mid + 1, r, Rson(id));}int query(int l, int r, int id){if (l == L(id) && R(id) == r)return Max(id);Down(id);int mid = (L(id) + R(id)) >> 1, ans ;if (r <= mid)ans = query(l, r, Lson(id));else if (mid < l)ans = query(l, r, Rson(id));else ans = max(query(l, mid, Lson(id)), query(mid + 1, r, Rson(id)));U(id);return ans;}void up(int l, int r, int val, int id){if (l == L(id) && R(id) == r){Max(id) = max(Max(id), val);Lazy(id) = max(Lazy(id), val);return;}Down(id);int mid = (L(id) + R(id)) >> 1;if (r <= mid)up(l, r, val, Lson(id));else if (mid < l)up(l, r, val, Rson(id));else {up(l, mid, val, Lson(id));up(mid + 1, r, val, Rson(id));}U(id);}vector<int>G;int hehehe;struct Edge{int l, r;}x[N];bool cmp(Edge a, Edge b){return a.r < b.r;}int n, m;int a[N], b[N];int main(){while (~scanf("%d", &n)){G.clear();for (int i = 1; i <= n; i++){rd(a[i]); rd(b[i]);x[i].l = a[i] – b[i];x[i].r = a[i] + b[i];G.push_back(x[i].l);G.push_back(x[i].r);}sort(G.begin(), G.end());G.erase(unique(G.begin(), G.end()), G.end());for (int i = 1; i <= n; i++){x[i].l = lower_bound(G.begin(), G.end(), x[i].l) – G.begin() + 1;x[i].r = lower_bound(G.begin(), G.end(), x[i].r) – G.begin() + 1;}sort(x + 1, x + n + 1, cmp);build(1, G.size(), 1);int ans = 1;for (int i = 1; i <= n; i++){int tmp = query(1, x[i].l, 1) + 1;ans = max(ans, tmp);up(x[i].r, x[i].r, tmp, 1);}pt(ans); puts("");}return 0;}
没有早一步，也没有晚一步，刚好遇上了你！
