贪心、二分、整体二分

注意到 $n,m,k$ 同阶，可以对每个国家二分答案得到 $O(n^2 \log n)$ 的做法。

采用整体二分优化，用树状数组维护差分后的空间站序列，每次检查时直接遍历每个国家的所有空间站，因为所有国家的空间站数量是 $O(n)$ 等级，分治 $O(\log n)$ 层每层枚举一遍的时间复杂度仍然可以接受。由于可能有国家无法达成目标，在原本的陨石雨下完后再下一场覆盖所有位置且陨石数量达到需求上界的雨即可，这样无法达成目标的国家的答案将是这一场雨的编号，输出时判断一下。极限情况下一个国家获得的陨石数量会爆 long long，求解过程中对 $10^9$ 取 $\min$ 即可。

用 vector 实现的空间复杂度为 $O(n \log n)$，精细一些的实现的空间复杂度为 $O(n)$，这里采用代码更短的 vector 实现。

总体时间复杂度 $O(n \log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
static constexpr int inf=1'000'000'000;
struct Rain{int l,r,w;}w[300'005];
int n,m,k,pos,a[300'005],ans[300'005];
vector<int> v[300'005];
long long c[300'005];
void add(int x,int y){while(x<=m) c[x]+=y,x+=x&-x;}
long long sum(int x){
    long long ret=0ll;
    while(x) ret+=c[x],x-=x&-x;
    return ret;
}
void raining(int x,int t){
    if(w[x].l>w[x].r) add(1,w[x].w*t);
    add(w[x].l,w[x].w*t),add(w[x].r+1,-w[x].w*t);
}
void overall_binary(vector<int> x,int l,int r){
    if(x.empty()) return;
    if(l==r){
        for(int i:x) ans[i]=l;
        return;
    }
    vector<int> vl,vr;
    int mid=(l+r)>>1;
    while(pos<mid) raining(++pos,1);
    while(pos>mid) raining(pos--,-1);
    for(int i:x){
        long long now=0ll;
        for(int j:v[i]) now=min(now+sum(j),1ll*inf);
        if(now>=a[i]) vl.push_back(i);
        else vr.push_back(i);
    }
    overall_binary(vl,l,mid),overall_binary(vr,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) v[a[i]].push_back(i);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&k);
    for(int i=1;i<=k;i++) scanf("%d%d%d",&w[i].l,&w[i].r,&w[i].w);
    ++k,w[k].l=1,w[k].r=m,w[k].w=inf;
    vector<int> u;
    for(int i=1;i<=n;i++) u.push_back(i);
    overall_binary(u,1,k);
    for(int i=1;i<=n;i++)
        if(ans[i]==k) puts("NIE");
        else printf("%d\n",ans[i]);
    return 0;
}