对陨石雨的轮数进行整体分治,如果当前陨石轮数mid的陨石数多于其中任意一个国家所需,那么进入值域[l,mid],否则进入[mid+1,r]。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<vector>
#define ll long long
#define gc getchar()
using namespace std;
const int N=3e5+10;
template<class o>
inline void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
vector<int>a[N];
ll c[N];int n,m,K,T,q[N],tmp[N],p[N];bool v[N];
int l[N],r[N];ll d[N];int ans[N];
inline void add(int x,ll k){for(;x<=m;x+=x&-x)c[x]+=k;}
inline ll ask(int x){ll ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
void ins(int i,int op)
{
    if(l[i]<=r[i])
        add(l[i],op*d[i]),add(r[i]+1,-op*d[i]);
    else
        add(r[i]+1,-op*d[i]),add(1,op*d[i]),add(l[i],op*d[i]);
}
void solve(int l,int r,int st,int ed)
{
    if(l==r){for(int i=st;i<=ed;i++)ans[q[i]]=l;return ;}
    int mid=l+r>>1,cnt=0;
    while(T<=mid)ins(++T,1);
    while(T>mid)ins(T--,-1);
    for(int i=st;i<=ed;i++)
    {
        int pos=q[i];ll sum=0;
        for(int j=0;j<a[pos].size();j++)
        {
            sum+=ask(a[pos][j]);
            if(sum>=p[pos])break;
        }
        if(sum>=p[pos])v[pos]=1,++cnt;
        else v[pos]=0;
    }
    int l1=st,l2=st+cnt;
    for(int i=st;i<=ed;i++)
        if(v[q[i]])tmp[l1++]=q[i];
        else tmp[l2++]=q[i];
    for(int i=st;i<=ed;i++)
        q[i]=tmp[i];
    solve(l,mid,st,l1-1);
    solve(mid+1,r,l1,ed);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    qr(n);qr(m);
    for(int i=1,x;i<=m;i++)qr(x),a[x].push_back(i);
    for(int i=1;i<=n;i++)q[i]=i,qr(p[i]);
    qr(K);T=0;
    for(int i=1;i<=K;i++)qr(l[i]),qr(r[i]),qr(d[i]);
    ++K;l[K]=1,r[K]=m,d[K]=1e9;
    solve(1,K,1,n);
    for(int i=1;i<=n;i++)
    {
        if(ans[i]!=K)qw(ans[i]),puts("");
        else printf("NIE\n");
    }
     
    return 0;
}