Description：

一个星球环形带上分为 $M$ 个区域， $n$ 个国家， $k$ 天，每个区域可能有若干国家的陨石收集器，每一天有一段连续区域下陨石雨， 其上所有收集器都为本国家收集到 $D_i$ 的陨石，每个国家有一定的陨石需求量 $P_i$ ，求每个国家第几天收集陨石量恰好满足需求。

$1\leqslant n,m,k\leqslant 3\times10^5,1\leqslant A_i,P_i<10^9$

Solution：

整体二分经典例题。

首先答案是满足可二分性的，但是单次对答案的判断是 $O(n)$ 的，因为要累加答案，所以我们可以用整体二分，对于当前的二分值 $mid$ ，把所有 $\leqslant mid$ 天的陨石都加进去，然后依次判断每个询问是否已经符合条件，如果符合，就放在右边，否则放在左边。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,k;

#define MAXN 600010

vector<int> o[MAXN];

struct option

{

	int type;

	int l1,r1,l2,r2,v;

	int id,sum;

}q[MAXN],q1[MAXN],q2[MAXN];

int tot = 0;

int p[MAXN];

inline int lowbit(int x){return x & (-x);}

int c[MAXN];

inline void add(int p,int x){for(register int i = p;i <= m;i += lowbit(i))c[i] += x;return;}

inline int query(int p){int res = 0;for(register int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

int ans[MAXN];

void solve(int l,int r,int L,int R)

{

	if(L == R)

	{

		for(register int i = l;i <= r;++i)if(q[i].type)ans[q[i].id] = L;

		return;

	}

	register int mid = ((L + R) >> 1);

	register int cnt1 = 0,cnt2 = 0;

	for(register int i = l;i <= r;++i)

	{

		if(q[i].type == 0)

		{

			if(q[i].id <= mid)

			{

				q1[++cnt1] = q[i];

				add(q[i].l1,q[i].v);add(q[i].r1 + 1,-q[i].v);

				add(q[i].l2,q[i].v);add(q[i].r2 + 1,-q[i].v);

			}

			else q2[++cnt2] = q[i];

		}

	}

	for(register int i = l;i <= r;++i)

	{

		if(q[i].type == 1)

		{

			register int res = 0;

			for(register vector<int>::iterator it = o[q[i].id].begin();it != o[q[i].id].end();++it)

			{

				res = res + query(*it);

				if(res >= q[i].sum)break;

			}

			if(res >= q[i].sum)

			{

				q1[++cnt1] = q[i];

			}

			else

			{

				q[i].sum -= res;

				q2[++cnt2] = q[i];

			}

		}

	}

	register int cur = l;

	for(register int i = 1;i <= cnt1;++i)

	{

		if(q1[i].type == 0)

		{

			add(q1[i].l1,-q1[i].v);add(q1[i].r1 + 1,q1[i].v);

			add(q1[i].l2,-q1[i].v);add(q1[i].r2 + 1,q1[i].v);

		}

	}

	for(register int i = 1;i <= cnt1;++i)q[cur++] = q1[i];

	for(register int i = 1;i <= cnt2;++i)q[cur++] = q2[i];

	solve(l,l + cnt1 - 1,L,mid);

	solve(l + cnt1,r,mid + 1,R);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)o[rd()].push_back(i);

	for(int i = 1;i <= n;++i)

	{

		++tot;q[tot].id = i;q[tot].type = 1;

		q[tot].sum = rd();

	}

	scanf("%d",&k);

	for(int i = 1;i <= k;++i)

	{

		++tot;q[tot].id = i;

		q[tot].l1 = rd();q[tot].r2 = rd();q[tot].v = rd();

		if(q[tot].l1 > q[tot].r2)q[tot].r1 = m,q[tot].l2 = 1;

		else q[tot].r1 = q[tot].l1,q[tot].l2 = q[tot].l1 + 1;

	}

	solve(1,tot,1,k + 1);

	for(int i = 1;i <= n;++i)

	{

		if(ans[i] <= k)printf("%d\n",ans[i]);

		else puts("NIE");

	}

	return 0;

}