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

P7424 天天爱射击 题解

P7424 天天爱射击题解