P7424 天天爱射击 题解
Sham_Sleep
2021-04-07 13:01:12
**整体二分**
------------
**题面简述**
有 $m$ 块木板，有 $n$ 颗子弹，每克子弹会穿过一个点，每块木板会覆盖一个区间，且有耐久值 $S$ ， 被穿过 $S$ 次就会破碎， 求颗子弹可以打碎多少木板。
------------
**思路**
------------
* step 1:
题意很简单，转化一下，不看子弹，而是看哪一块木板在哪个子弹打来的时候碎。
再转换一下，将每个子弹看成一个时间点，那么就是求木板破碎的时间。那么题目很简单了。
那就是求每颗子弹对每个木板的贡献。
------------
* step 2 :
问题转化成每块木板被击碎的时间，考虑离线做法。
将木板看成询问操作，子弹看成修改操作，又因为是求区间前 $S$ 个，是不是很熟悉？ ~~甲方爸爸又开口了，又是惯用伎俩~~。 所以考虑整体二分。
又考虑到有些木板从头至尾都未被击碎，所以值域考虑[1, $m+1$ ] 在 $m+1$ 全部击碎。
------------
**代码如下**
```
#include <stdio.h>
#include <iostream>
const int N = 2e5 + 5;
struct node {
int l, r, pos, val, id, ans, t, cur;
//id = 1代表子弹
//id = 2代表木板
} q[N << 1], temp[N << 1];
int n, m, top, Max;
int tree[N], tmp[N << 1], ans[N];
bool mark[N << 1];
int lowbit(int k) {return k & (-k);}
void add(int idx, int val) {
while(idx <= Max) {
tree[idx] += val;
idx += lowbit(idx);
}
return ;
}
int sum(int idx) {
int s = 0;
while(idx) {
s += tree[idx];
idx -= lowbit(idx);
}
return s;
}
//统计子弹位置考虑用树状数组。
//x的值域在2e5之内，完全开得下
void Binsea(int l, int r, int L, int R) {
if(L > R || l > r) return ;
int mid = L + R >> 1, o = 0;
if(L == R) {
for(int i = l; i <= r; ++i)
if(q[i].id == 2) q[i].ans = L;
return ;
}
for(int i = l; i <= r; ++i) {
if(q[i].t <= mid && q[i].id == 1) add(q[i].pos, 1);
if(q[i].id == 2) tmp[i] = sum(q[i].r) - sum(q[i].l - 1);
}
for(int i = l; i <= r; ++i)
if(q[i].t <= mid && q[i].id == 1) add(q[i].pos, -1);
for(int i = l; i <= r; ++i) {
if(q[i].id == 1) {
if(q[i].t <= mid) mark[i] = true, ++o;
else mark[i] = false;
}
else {
if(tmp[i] + q[i].cur >= q[i].val) mark[i] = true, ++o;
else mark[i] = false, q[i].cur += tmp[i];
}
}
int i = l, j = l + o;
for(int k = l; k <= r; ++k) {
if(mark[k]) temp[i++] = q[k];
else temp[j++] = q[k];
}
for(int k = l; k <= r; ++k) q[k] = temp[k];
Binsea(l, i - 1, L, mid);
Binsea(i, j - 1, mid + 1, R);
return ;
}
int main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
std :: ios :: sync_with_stdio(false);
std :: cin >> n >> m;
for(int i = 1; i <= n; ++i) {
std :: cin >> q[i + m].l >> q[i + m].r >> q[i + m].val;
Max = std :: max(Max, q[i + m].r);
q[i + m].id = 2;
}
//注意修改操作一定要放在询问操作之前，否则无法计算贡献
for(int i = 1; i <= m; ++i) {
std :: cin >> q[i].pos;
q[i].id = 1;
q[i].t = i;
}
Binsea(1, n + m, 1, m + 1);
for(int i = 1; i <= n + m; ++i)
if(q[i].id == 2) ++ans[q[i].ans];
for(int i = 1; i <= m; ++i)
std :: cout << ans[i] << '\n';
return 0;
}
```
望管理员大大通过QAQ，码题解不容易QAQ