记录编号	590802	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	天天爱射击	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	5.068 s
提交时间	2024-07-11 17:29:55	内存使用	10.42 MiB

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;

int n,m;

struct wood{
    int l,r,s,id;
}b[maxn],b1[maxn],b2[maxn];

int a[maxn],ans[maxn],pos[maxn],c[maxn],ma;

void add(int x,int y){
    for(;x<=ma;x+=x&-x){
        c[x]+=y;
    } 
}

int ask(int x){
    int s=0;
    for(;x;x-=x&-x){
        s+=c[x];
    }    
    return s;
}

void solve(int l,int r,int l2,int r2){
    if(l2>r2) return;
    if(l==r){
        for(int i=l2;i<=r2;i++){
            pos[b[i].id]=l;
        }
        return;
    }
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++){
        add(a[i],1);
    }
    int cnt1=0,cnt2=0;
    for(int i=l2;i<=r2;i++){
        int k=ask(b[i].r)-ask(b[i].l-1);
        if(k>=b[i].s){
            cnt1++;
            b1[cnt1]=b[i];
        }
        else{
            b[i].s-=k;
            cnt2++;
            b2[cnt2]=b[i];
        }
    }
    for(int i=1;i<=cnt1;i++){
        b[i+l2-1]=b1[i];
    }
    for(int i=1;i<=cnt2;i++){
        b[i+l2+cnt1-1]=b2[i];
    }
    for(int i=l;i<=mid;i++){
        add(a[i],-1);
    }
    solve(l,mid,l2,l2+cnt1-1);
    solve(mid+1,r,l2+cnt1,r2);
}

int main(){
    freopen("shooting.in","r",stdin);
    freopen("shooting.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].s);
        b[i].id=i; 
        ma=max(ma,b[i].r);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    solve(1,m+1,1,n);
    for(int i=1;i<=n;i++){
        ans[pos[i]]++;
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}