题目大意：
给定一个环，每个环上节点有一个所属国家，\(k\)次事件，每次对\([l,r]\)区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值
\(1≤n,m,k≤3*10^5,1≤p_i,a_i≤10^9\)
值得一提的是这提的空间限制是\(64.5MB\)，这样一些奇怪的树据截垢就被卡掉了
其实我们可以考虑整体二分！
我们二分时间轴，然后处理国家
构造函数\(solve(tl,tr,l,r)\)表示在\([tl,tr]\)场陨石雨内，还有\([l,r]\)个国家没有确定答案
在每个\(solve\)内，先将\([tl,mid]\)内的陨石全部落下，然后判断\([l,r]\)内的国家是否满足要求，达到数目的国家分治进左侧，未达到的国家分治进右侧
考虑一个国家可能对应多个节点，其实只要用链表存在然后单点查询就好了，毕竟每一层的查询次数之和一定是\(m\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) (i&-i)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=3e5+10,inf=1e9;
int n,m,ask,cnt;
struct point
{
int l,r,k;
}q[N*3];
struct node
{
int up,id;
}g[N],g1[N],g2[N];
int up[N],ret[N];
int tr[N<<1];
vector<int> rose[N];
inline void add(int x,int k)
{
for(int i=x;i<=2*m;i+=lowbit(i)) tr[i]+=k;
}
inline int query(int y)
{
int ret=0;
for(int i=y;i;i-=lowbit(i)) ret+=tr[i];
return ret;
}
inline void solve(int tl,int tr,int l,int r)
{
if(l>r) return;
if(tl==tr)
{
for(int i=l;i<=r;++i)
ret[g[i].id]=tl;
return;
}
int mid=(tl+tr)>>1,cnt1=0,cnt2=0,tmp;
for(int i=tl;i<=mid;++i)
{
add(q[i].l,q[i].k);
add(q[i].r+1,-q[i].k);
}
for(int sum,i=l;i<=r;++i)
{
sum=rose[g[i].id].size(),tmp=0;
for(int k=0;k<sum;++k)
{
tmp+=query(rose[g[i].id][k])+query(rose[g[i].id][k]+m);
if(tmp>g[i].up) break;
}
if(g[i].up<=tmp) g1[++cnt1]=g[i];
else g[i].up-=tmp,g2[++cnt2]=g[i];
}
for(int i=tl;i<=mid;++i) add(q[i].l,-q[i].k),add(q[i].r+1,q[i].k);
for(int i=1;i<=cnt1;++i) g[l+i-1]=g1[i];
for(int i=1;i<=cnt2;++i) g[l+i+cnt1-1]=g2[i];
solve(tl,mid,l,l+cnt1-1);
solve(mid+1,tr,l+cnt1,r);
}
inline void main()
{
n=read(),m=read();
for(int i=1;i<=m;++i) rose[read()].push_back(i);
for(int i=1;i<=n;++i) g[i].up=read(),g[i].id=i;
ask=read();
for(int l,r,k,i=1;i<=ask;++i)
{
l=read(),r=read(),k=read();
if(r<l) r+=m;
q[++cnt]=(point){l,r,k};
}
solve(1,cnt+1,1,n);
for(int i=1;i<=n;++i)
{
if(ret[i]>ask) puts("NIE");
else printf("%d\n",ret[i]);
}
}
}
signed main()
{
red::main();
return 0;
}