题目

#include <iostream>
#include <algorithm>
using namespace std;
const int maxx = 2e8+5;
struct node {
    int l, r, t;
}p[100005];
int n;
int cnt;
int maxv[3000005];
int ls[3000005];
int rs[3000005];
unordered_map<int, int> m;
inline int max(int a, int b) {
    return a > b ? a : b;
}
void pushup(int p) {
    maxv[p] = max(maxv[ls[p]], maxv[rs[p]]);
}
bool cmp(node a, node b) {
    return a.l < b.l;
}
int update(int l, int r, int x, int val, int p) {
    if (p == 0) p = ++cnt;
    if (l >= r) {
        maxv[p] = val; 
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ls[p] = update(l, mid, x, val, ls[p]);
    else rs[p] = update(mid + 1, r, x, val, rs[p]);
    pushup(p);
    return p;
}
int query(int l, int r, int x, int y, int p) {
    if (p == 0) return 0;
    if (x <= l && r <= y) {
        return maxv[p];
    }
    int res = 0;
    int mid = (l + r) >> 1;
    if (x <= mid) res = max(res, query(l, mid, x, y, ls[p]));
    if (y > mid) res = max(res, query(mid + 1, r, x, y, rs[p]));
    return res;
}
int ans[1000005];
int main() {
    scanf("%d", &n);
  
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].l, &p[i].r);
        p[i].r += p[i].l;
        p[i].t = i;
    }
    sort(p + 1,p + 1 + n, cmp);
 
    for (int i = n; i >= 1; i--) {
        int l = p[i].l;
        int r = p[i].r;
        int f = query(-maxx, maxx, l + 1, r - 1, 1);
        if (f == 0) f = i;
        update(-maxx, maxx, l, f, 1);
        ans[p[i].t] = f - i + 1;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}