题目
题解
整体二分,对于一个时间区间$[l,r]$先把$[1,mid]$的子弹加入树状数组,然后就是区间查询是否满足条件了
注意最后处理时间点$m$的时候所有前面没碎的木板都在这个点上,所以要检验是否合法(即到最后是否碎掉)
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+5;
struct p{
int x,x_,s;
}bl[MAX];
int n,m,N;
int pos[MAX],s[MAX],Tm[MAX],id[MAX],_id[MAX];
int lowbit(int x) {return x&-x;}
void change(int x,int d=1) {for(int i=x;i<=N;s[i]+=d,i+=lowbit(i));}
int ask(int x)
{
int ans=0;
for(int i=x;i;ans+=s[i],i-=lowbit(i));
return ans;
}
int ask(int l,int r) {return ask(r)-ask(l-1);}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void Solve(int l=1,int r=m,int L=1,int R=n)
{
if(l==r)
{
change(pos[l]);
int ans=0;
if(l==m)
{
for(int i=L;i<=R;++i)
if(ask(bl[id[i]].x,bl[id[i]].x_)>=bl[id[i]].s) ++ans;
}
else ans=R-L+1;
return void(printf("%d\n",ans));
}
for(int i=l;i<=mid;++i)
change(pos[i]);
int cnt=L-1;
for(int i=L;i<=R;++i)
{
Tm[i]=ask(bl[id[i]].x,bl[id[i]].x_);
if(Tm[i]>=bl[id[i]].s) _id[++cnt]=id[i];
}
int Mid=cnt;
for(int i=L;i<=R;++i)
if(Tm[i]<bl[id[i]].s) _id[++cnt]=id[i];
for(int i=L;i<=R;++i)
id[i]=_id[i];
for(int i=l;i<=mid;++i)
change(pos[i],-1);
Solve(l,mid,L,Mid),Solve(mid+1,r,Mid+1,R);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
id[i]=i,bl[i].x=read(),N=max(N,bl[i].x_=read()),bl[i].s=read();
for(int i=1;i<=m;++i)
N=max(N,pos[i]=read());
return Solve(),0;
}