给每个国家建一个链表,这样分治过程中的复杂度就和序列长度线形相关了,无脑套整体二分就可以。
（最坑的地方是如果所有位置都是一个国家，那么它的样本个数会爆longlong！！被这个坑了一次，大于p[i]的时候break就行了）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 300005
#define int long long
using namespace std;
int n,m,k;
vector<int>a[N];
int c[N];
void add(int x,int y)
{
for(int i=x;i<=m;i+=(i&(-i)))
{
c[i]+=y;
}
}
int qur(int x)
{
int ans=;
for(int i=x;i;i-=(i&(-i)))
{
ans+=c[i];
}
return ans;
}
int q[N];
int p[N];
struct node
{
int l,r,z;
}op[N];
int ans[N];
int tmp[][N];
void solve(int L,int R,int l,int r)
{
if(L>R)return ;
if(l==r)
{
for(int i=L;i<=R;i++)
{
ans[q[i]]=l;
}
return ;
}
int mid=(l+r)>>;
int cnt1=,cnt2=;
for(int i=l;i<=mid;i++)
{
if(op[i].l<=op[i].r)
{
add(op[i].l,op[i].z);add(op[i].r+,-op[i].z);
}
else
{
add(,op[i].z);add(op[i].r+,-op[i].z);add(op[i].l,op[i].z);
}
}
for(int i=L;i<=R;i++)
{
int tp=;
for(int j=;j<a[q[i]].size();j++)
{
tp+=qur(a[q[i]][j]);
if(tp>=p[q[i]])break;
}
if(tp>=p[q[i]])tmp[][++cnt1]=q[i];
else p[q[i]]-=tp,tmp[][++cnt2]=q[i];
}
for(int i=l;i<=mid;i++)
{
if(op[i].l<=op[i].r)
{
add(op[i].l,-op[i].z);add(op[i].r+,op[i].z);
}
else
{
add(,-op[i].z);add(op[i].r+,op[i].z);add(op[i].l,-op[i].z);
}
}
int l1=L+cnt1-;
for(int i=;i<=cnt1;i++)q[L+i-]=tmp[][i];
for(int i=;i<=cnt2;i++)q[l1+i]=tmp[][i];
solve(L,l1,l,mid);solve(l1+,R,mid+,r);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=;i<=m;i++)
{
int t1;scanf("%lld",&t1);
a[t1].push_back(i);
}
for(int i=;i<=n;i++)scanf("%lld",&p[i]),q[i]=i;
scanf("%lld",&k);
for(int i=;i<=k;i++)
{
scanf("%lld%lld%lld",&op[i].l,&op[i].r,&op[i].z);
}
solve(,n,,k+);
for(int i=;i<=n;i++)
{
if(ans[i]!=k+)printf("%lld\n",ans[i]);
else puts("NIE");
}
return ;
}