P7424 「天天爱射击」

~~天天爱音击~~

题目描述

小 C 爱上了一款名字叫做《天天爱射击》的游戏。如图所示，这个游戏有一些平行于轴的木板。现在有一些子弹，按顺序沿着轴方向向这些木板射去。第块木板被个子弹贯穿以后，就会碎掉消失。一个子弹可以贯穿其弹道上的全部木板，特别的，如果一个子弹触碰到木板的边缘，也视为贯穿木板。

小 C 现在知道了游戏中块木板位置，以及知道了个子弹射击位置。现在问你每个子弹射出去以后，有多少木板会碎掉？

输入格式

从标准输入读入数据。

第一行两个整数和，表示木板数量和子弹数量。其中。

接下来行，每行三个整数，表示每块木板的左端点坐标、右端点坐标，以及贯穿多少次会碎掉。其中保证。

接下来行，每行一个整数，表示每个子弹的坐标。子弹按照发射顺序给出。其中保证。

输出格式

输出到标准输出。

行，每行一个整数。表示每颗子弹射出去后，有多少木板碎掉。

SAMPLE I/O

I

O

1
2

1
2

思路

看到这个题目，感觉只看这个题目做不出来，我们考虑把他转换一下：

第块木板被个子弹贯穿以后，就会碎掉消失。那么我们可以把这个条件看成：经过这个木板的坐标区间的第个子弹会把第块木板贯穿。容易发现，给这些子弹以时间为关键字进行排序，就变成了找这些子弹的第小值的子弹的编号。再加上是找某个区间的第小值，那么就变成了区间第小值问题。这不就是可持久化线段树解决的经典问题吗？我们可以把这些子弹的坐标和发射时间转化成可持久化值域线段树，然后来解决。

具体过程是：

首先把这些子弹按照他们的发射坐标存进一个 vector<int> t[N] 里，第一维存的是他的发射坐标，然后把这些子弹按照时间顺序push到 t[i] 里。然后就可以建一个主席树，rt[i] 表示坐标区间 , 然后是一个值域主席树，他的值存的是时间。然后我们就可以求区间第小时间发射的子弹，他刚好贯穿了这个木板，然后给这个子弹的答案。最后输出答案即可。

代码如下：

#include<bits/stdc++.h>
#define technopolis2085 return 0
using namespace std;
const int N = 2e5+10;
const int M = 80*N;
struct node{
    int l, r, val;
}tr[M];
struct Plank{
    int l, r, k;
    //注意这里的被贯穿第k次才能死的机制可以被用于查区间第k小（关键字是时间）
}plank[N];
int n, m;

int rt[N];
int idx;
void insert(int x, int &y, int l, int r, int w){
    y = ++idx;
    tr[y] = tr[x];
    tr[y].val ++;
    if(l==r) return ;
    int mid = l+r>>1;
    if(w<=mid) insert(tr[x].l, tr[y].l, l, mid, w);
    else insert(tr[x].r, tr[y].r, mid+1, r, w);
}

int query(int x, int y, int l, int r, int k){
    if(l==r) return l;
    int mid = l+r>>1;
    int q = tr[tr[y].l].val - tr[tr[x].l].val;
    if(q>=k) return query(tr[x].l, tr[y].l, l, mid, k);
    else return query(tr[x].r, tr[y].r, mid+1, r, k-q);
}
vector<int> times[N];
//这里的times[i][j]表示第j个在i位置射出的子弹的时间为times[i][j];
int ans[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>plank[i].l>>plank[i].r>>plank[i].k;
    }
    int bulletpos;
    for(int i=1;i<=m;i++){
        cin>>bulletpos;
        times[bulletpos].push_back(i);
    }
    
    int maxn = 2e5+2;
    for(int i=1;i<=maxn;i++){
        if(times[i].size() == 0) times[i].push_back(m+1);
    }
    for(int i=1;i<=maxn;i++){
        rt[i] = rt[i-1];
        for(int j=0;j<times[i].size();j++){
            insert(rt[i], rt[i], 1, m+1, times[i][j]);
        }
    }
    
    for(int i=1;i<=n;i++){
        int res = query(rt[plank[i].l - 1], rt[plank[i].r], 1, m+1, plank[i].k);
        if(res == m+1) continue;
        ans[res] ++;
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }

    technopolis2085;
}