题意：一条直线上有n个炸弹，给出每个炸弹的爆炸半径，可以引爆另一个炸弹爆炸。问：每个炸弹爆炸后，最多有几个炸弹一起爆炸？
迭代，用线段树更新。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #define ll long long 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define X first 8 #define Y second 9 #define mp make_pair 10 #define pii pair<int, int> 11 #define gg puts("gg"); 12 using namespace std; 13 const int N = 1e5+5; 14 struct p{ 15 int n, pos, ra; 16 p(){} 17 p(int pos, int ra):pos(pos), ra(ra){} 18 }; 19 bool cmppos(p A, p B){ 20 return A.pos < B.pos; 21 } 22 23 p pp[N]; 24 //after sort 25 int pos[N]; 26 int lpos[N], rpos[N], now; 27 28 struct Node{ 29 int l, r; 30 Node(){} 31 Node(int l, int r):l(l), r(r){} 32 }; 33 Node T[N<<2]; 34 void pushup(int rt){ 35 T[rt].l = min(T[rt<<1].l, T[rt<<1|1].l); 36 T[rt].r = max(T[rt<<1].r, T[rt<<1|1].r); 37 } 38 void gao(Node& x, Node y){ 39 if(x.l > y.l) x.l = y.l; 40 if(x.r < y.r) x.r = y.r; 41 } 42 void update(int x, Node y, int l, int r, int rt){ 43 if(x == l&&x == r){ 44 T[rt] = y; 45 return ; 46 } 47 int m = l+r >> 1; 48 if(x <= m) update(x, y, lson); 49 else update(x, y, rson); 50 pushup(rt); 51 } 52 void build(int l, int r, int rt){ 53 if(l == r){ 54 T[rt].l = lpos[now]; 55 T[rt].r = rpos[now]; 56 now++; 57 return ; 58 } 59 int m = l+r >> 1; 60 build(lson); 61 build(rson); 62 pushup(rt); 63 } 64 void query(Node& ans, int L, int R, int l, int r, int rt){ 65 if(L <= l&& r <= R){ 66 gao(ans, T[rt]); 67 return ; 68 } 69 int m = l+r >> 1; 70 if(L <= m) query(ans, L, R, lson); 71 if(m < R) query(ans, L, R, rson); 72 } 73 int ans[N]; 74 void debug(int i){ 75 printf("%d: lpos:%d, rpos:%d ", i, lpos[i], rpos[i]); 76 } 77 78 int main(){ 79 int n; 80 while(scanf("%d", &n), n){ 81 for(int i = 1; i <= n; i++){ 82 pp[i].n = i; 83 scanf("%d%d", &pp[i].pos, &pp[i].ra); 84 pos[i] = pp[i].pos; 85 } 86 sort(pos+1, pos+n+1); 87 sort(pp+1, pp+n+1, cmppos); 88 89 for(int i = 1; i <= n; i++) 90 lpos[i] = pp[i].pos-pp[i].ra, rpos[i] = pp[i].pos+pp[i].ra; 91 92 now = 1; 93 build(1, n, 1); 94 95 bool tag = true; 96 while(tag){ 97 tag = false; 98 for(int i = 1; i <= n; i++){ 99 int lcan = lower_bound(pos+1, pos+n+1, lpos[i])-pos, rcan = upper_bound(pos+1, pos+n+1, rpos[i])-pos-1; 100 ans[ pp[i].n ] = rcan-lcan+1; 101 Node ret = Node(2e9, -2e9); 102 query(ret, lcan, rcan, 1, n, 1); 103 if(lpos[i] > ret.l||rpos[i] < ret.r) { 104 tag = true; 105 if(lpos[i] > ret.l) lpos[i] = ret.l; 106 if(rpos[i] < ret.r) rpos[i] = ret.r; 107 update(i, ret, 1, n, 1); 108 } 109 } 110 } 111 for(int i = 1; i <= n; i++) 112 printf("%d%c", ans[i], " "[i == n]); 113 } 114 return 0; 115 }