[THUPC2017] 天天爱射击 题解

俗话说的好，正难则反，既然不好想每一个子弹能打碎多少个木板，不如想每个木板被那枚子弹打碎。

然后就是显然的整体二分。由于可能木板不会被击碎，那些木板的分数会累加到最后一个子弹上，因此我们可以加一枚背锅弹，承担多余的分数。

时间复杂度 \(O((n+m)\log^2 m)\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n,m,c[N],sm[N];
struct que{int l,r,s,o,id;
}q[N*2],q1[N*2],q2[N*2];
void add(int x,int k){for(;x<=m+1;x+=x&-x)c[x]+=k;
}int sum(int x){if(!x) return 0;int re=0;for(;x;x-=x&-x)re+=c[x];return re;
}void dichot(int l,int r,int ql,int qr){if(ql>qr) return;if(l==r){for(int i=ql;i<=qr;i++)if(!q[i].o) sm[l]++;return;}int t1=0,t2=0,mid=(l+r)/2;for(int i=ql;i<=qr;i++){if(q[i].o){if(q[i].id<=mid){add(q[i].s,1);q1[++t1]=q[i];}else q2[++t2]=q[i];continue;}int x=sum(q[i].r)-sum(q[i].l-1);if(q[i].s>x){q[i].s-=x;q2[++t2]=q[i];}else q1[++t1]=q[i];}for(int i=1;i<=t1;i++){if(q1[i].o) add(q1[i].s,-1);q[i+ql-1]=q1[i];}for(int i=1;i<=t2;i++)q[i+ql+t1-1]=q2[i];dichot(l,mid,ql,ql+t1-1);dichot(mid+1,r,ql+t1,qr);
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=m+1;i<=n+m;i++)cin>>q[i].l>>q[i].r>>q[i].s;for(int i=1;i<=m;i++)cin>>q[i].s,q[i].id=i,q[i].o=1;dichot(1,m+1,1,n+m);for(int i=1;i<=m;i++)cout<<sm[i]<<"\n";return 0;
}//Kaká