题解 SP10264 METEORS - Meteors

整体二分经典题，所以我们用分块解决

Solution

和整体二分类似，我们把 \(k\) 次操作分成 \(\sqrt k\) 块，每一块一起考虑。对于区间加，可以转化为差分，那么在每个块一起作差分后再作前缀和即可得到当前操作块后每段路的陨石个数，然后加进其所属国家的总个数。接着看一遍所有国家，如果在这整块操作后陨石个数已满足要求，就说明满足的时间就在这块之内，直接暴力倒着扫一遍这块操作，找到具体满足的时间即可。

怎么倒着扫一遍操作呢，之前不是用差分来转化的吗？由于只考虑当前国家，每个操作只用逐个判断这个国家的每段路是否在操作区间内，如果在就给国家总个数减去，减到小于需求就说明当前操作的时间即为答案。

统计 \(\sqrt k\) 次差分前缀和，且每个国家只会暴力倒着扫一次，复杂度为 \(\mathcal O((m+n)\sqrt k)\)。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
int n,m,q,blo,tot,bel[N],ans[N],p[N],ql[N],qr[N],qw[N];
ll sum[N],d[N],a[N];
vector<int>v[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=m;i++){
        scanf("%d",&x);
        v[x].push_back(i);
        bel[i]=x;
    }for(int i=1;i<=n;i++)scanf("%d",p+i);
    scanf("%d",&q);blo=sqrt(q);tot=q/blo+(q%blo!=0);
    for(int i=1;i<=q;i++)scanf("%d%d%d",ql+i,qr+i,qw+i);
    memset(ans,-1,sizeof(ans));
    for(int i=1;i<=tot;i++){
        int L=(i-1)*blo+1,R=min(q,i*blo);
        for(int j=L;j<=R;j++)//每块操作转化为差分
            if(ql[j]<=qr[j])d[ql[j]]+=qw[j],d[qr[j]+1]-=qw[j];
            else d[ql[j]]+=qw[j],d[m+1]-=qw[j],d[1]+=qw[j],d[qr[j]+1]-=qw[j];
        memset(sum,0,sizeof(sum));
        for(int j=1;j<=m;j++)a[j]=a[j-1]+d[j],sum[bel[j]]+=a[j];
        for(int k=1;k<=n;k++){
            if(ans[k]>=0||sum[k]<p[k])continue;
            ll s=sum[k];
            for(int j=R;j>=L;j--){//倒着扫
                for(int x:v[k]){
                    if(ql[j]<=qr[j])if(ql[j]<=x&&x<=qr[j])s-=qw[j];
                    if(ql[j]>qr[j])if(ql[j]<=x||x<=qr[j])s-=qw[j];
                }if(s<p[k]){ans[k]=j;break;}
            }
        }
    }for(int i=1;i<=n;i++)ans[i]>=0?printf("%d\n",ans[i]):puts("NIE");
    return 0;
}