[文章目录]
Description
有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。1<=n,m,k<=3*10^5 1<=Pi<=10^9 1<=Ai< 10^9
整体二分，分治K场陨石的同时分治国家。
求左区间陨石雨对每个国家的贡献，对于答案在左区间的国家进入左区间分治，否则进入右区间分治。
由于对于分治陨石雨的log层每个国家所在的每个位置都只会被查询一次，所以复杂度是对的。时间复杂度
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 301000
#define pb push_back
const int inf=0x3f3f3f3f;
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char f=1,ch=nc();
while(!isdigit(ch)) {if(ch=='-') f=0; ch=nc();}
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return f ? re:-re;
}
int n,m,M,cg[N],t[N],o[N],p[N],ans[N];
vector <int> ve[N];
struct node
{
int l,r,w;
}a[N];
ll s[N<<2];
void fix(int l,int r,int w)
{
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) s[l^1]+=w;
if(r&1) s[r^1]+=w;
}
}
ll query(int x)
{
ll re=0;
for(x=x+M;x;x>>=1) re+=s[x];
return re;
}
void solve(int l,int r,int L,int R)
{
if(l==r)
{
for(int i=L;i<=R;++i) ans[cg[i]]=l;
return ;
}
int mid=(l+r)>>1;
for(int i=l;i<=mid;++i)
{
if(a[i].l<=a[i].r) fix(a[i].l,a[i].r,a[i].w);
else fix(1,a[i].r,a[i].w),fix(a[i].l,m,a[i].w);
}
ll tmp; int i1=L,i2=R;
for(int i=L;i<=R;++i)
{
tmp=0;
for(int j=0;j<(int)ve[cg[i]].size();++j)
{
tmp+=query(ve[cg[i]][j]);
if(tmp>=p[cg[i]]){t[i1++]=cg[i]; break;}
}
if(tmp<p[cg[i]]) p[cg[i]]-=tmp,t[i2--]=cg[i];
}
for(int i=L;i<=R;++i) cg[i]=t[i];
for(int i=l;i<=mid;++i)
{
if(a[i].l<=a[i].r) fix(a[i].l,a[i].r,-a[i].w);
else fix(1,a[i].r,-a[i].w),fix(a[i].l,m,-a[i].w);
}
if(i2>=L) solve(l,mid,L,i2);
if(i1<=R) solve(mid+1,r,i1,R);
}
int main()
{
n=read(); m=read();
for(M=1;M<(m+1);M<<=1);
for(int i=1;i<=m;++i) ve[read()].pb(i);
for(int i=1;i<=n;++i) cg[i]=i,p[i]=read();
int t=read();
for(int i=1;i<=t;++i) a[i].l=read(),a[i].r=read(),a[i].w=read();
++t; a[t].l=1; a[t].r=m; a[t].w=inf;
solve(1,t,1,n);
for(int i=1;i<=n;++i)
{
if(ans[i]==t) puts("NIE");
else printf("%d\n",ans[i]);
}
return 0;
}