#include<bits/stdc++.h>
#define maxn 400005
using namespace std;
int n,m,l1[maxn],r1[maxn],kth[maxn],tot,ans[maxn],tree[maxn],ask[maxn],mx=2e5;
struct node
{
int id,l,r,num,k;
}q[maxn],q1[maxn],q2[maxn];
void update(int x,int k)
{
while(x<=mx)
{
tree[x]+=k;
x+=x&(-x);
}
return;
}
int query(int x)
{
int sum=0;
while(x)
{
sum+=tree[x];
x-=x&(-x);
}
return sum;
}
void solve(int ql,int qr,int l,int r)
{
if(ql>qr||l>r) return;
if(ql==qr)
{
for(int i=l;i<=r;i++)
{
if(!q[i].id&&q[i].l<=ask[ql]&&q[i].r>=ask[ql]) ans[ql]++;
}
return;
}
int mid=ql+qr>>1,tot1=0,tot2=0;
for(int i=l;i<=r;i++)
{
if(q[i].id)
{
if(q[i].id<=mid) update(q[i].num,1),q1[++tot1]=q[i];
else q2[++tot2]=q[i];
}
else
{
int res=query(q[i].r)-query(q[i].l-1);
if(res>=q[i].k) q1[++tot1]=q[i];
else q[i].k-=res,q2[++tot2]=q[i];
}
}
for(int i=1;i<=tot1;i++)
{
if(q1[i].id) update(q1[i].num,-1);
}
for(int i=1;i<=tot1;i++)
{
q[l+i-1]=q1[i];
}
for(int i=1;i<=tot2;i++)
{
q[l+tot1+i-1]=q2[i];
}
solve(ql,mid,l,l+tot1-1);
solve(mid+1,qr,l+tot1,l+tot1+tot2-1);
return;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>l1[i]>>r1[i]>>kth[i];
}
for(int i=1;i<=m;i++)
{
cin>>ask[i];
q[++tot]=(node){i,0,0,ask[i],0};
}
for(int i=1;i<=n;i++)
{
q[++tot]=(node){0,l1[i],r1[i],0,kth[i]};
}
solve(1,m,1,tot);
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
而且所有错误的点都是在200000行(也就是最后一行)的答案错了,不知道为什么。