§ 题意简述

给定 $n$ 个主体，每个主体有一个指标。给定 $m$ 个区域（环形），每个区域都分别属于不同的主体，有 $k$ 个区间加法，问每个主体在第几次区间修改后达成指标。

§ 题解

这道题有一点绕，首先我们搞清楚概念，具体看题意简述。

显然每个询问都能够二分解决，于是我们考虑用整体二分来整这道题。

首先确定整体二分的值域即我们二分的答案。

因为询问问的是天数，所以我们用 1 到 $k$ 作为我们整体二分的值域。

我们设整体二分的函数为 $\mathrm{solve}(L,R,l,r)$，其中 $L,R$ 表示值域，$l,r$ 表示询问。

对于当前二分到的值域区间 $L,R,M=(L+R)/2$，如果 $[L,M]$ 的修改操作能够直接使得询问达成指标，则我们把这个询问放进询问区间 $[l,m]$ 里，其中 $m=(l+r)/2$。

最后还原一下修改即可。

修改操作可以用树状数组+差分来实现，线段树也可以。

如何判断无解的情况呢？

我们可以加入一个虚拟的修改操作，即让区间 $[1,m]$ 加上无穷大，让修改操作的个数 $k$ 加一，最后输出答案的时候判断如果等于 $k$ 即是无解。

#include <cstdio>
#include <vector>
#define int long long
#define vec(x) (Q[x].G)

using namespace std;

const int Maxn = 3e5 + 5;
int n, m, k, qls[Maxn], qrs[Maxn], qva[Maxn], ans[Maxn], isa[Maxn];
struct Query_Node
{
	int w, id;
	vector < int > G;
} Q[Maxn], lq[Maxn], rq[Maxn];
struct Fenwick_Tree
{
	int bit[Maxn];
	
	void ins(int x, int v)
	{
		for (; x <= m; x += x & -x) 	bit[x] += v;
	}
	
	int ret(int x)
	{
		int res = 0;
		for (; x; x -= x & -x)	res += bit[x];
		return res;
	}
} fwt;

void solve(int lval, int rval, int st, int ed)
{
	if (lval > rval || st > ed) 	return ;
	if (lval == rval)
	{
		for (int i = st; i <= ed; ++i)	ans[Q[i].id] = lval;
		return ;
	}
	int mid = (lval + rval) >> 1;
	int lt = 0, rt = 0;
	for (int i = lval; i <= mid; ++i)
	{
		if (qls[i] <= qrs[i])
		{
			fwt.ins(qls[i], qva[i]);
			fwt.ins(qrs[i] + 1, -qva[i]);
		}
		else
		{
			fwt.ins(qls[i], qva[i]);
			fwt.ins(m + 1, -qva[i]);
			fwt.ins(1, qva[i]);
			fwt.ins(qrs[i] + 1, -qva[i]);
		}
	}
	for (int i = st; i <= ed; ++i)
	{
		int lim = 0;
		for (unsigned j = 0; j < vec(i).size(); ++j)
		{
			int mbr = vec(i)[j];
			int xxx = fwt.ret(mbr);
			lim += xxx;
			if (xxx > 1e9)	break;
		}
		if (lim >= Q[i].w)	lq[++lt] = Q[i];
		else	rq[++rt] = Q[i];
	}
	for (int i = 1; i <= lt; ++i)	Q[st + i - 1] = lq[i];
	for (int i = 1; i <= rt; ++i)	Q[st + lt + i - 1] = rq[i];
	if (rt) 	solve(mid + 1, rval, st + lt, ed);
	for (int i = lval; i <= mid; ++i)
	{
		if (qls[i] <= qrs[i])
		{
			fwt.ins(qls[i], -qva[i]);
			fwt.ins(qrs[i] + 1, qva[i]);
		}
		else
		{
			fwt.ins(qls[i], -qva[i]);
			fwt.ins(m + 1, qva[i]);
			fwt.ins(1, -qva[i]);
			fwt.ins(qrs[i] + 1, qva[i]);
		}
	}
	if (lt) 	solve(lval, mid, st, st + lt - 1);
}

signed main()
{
	scanf("%lld %lld", &n, &m);
	for (int i = 1, x; i <= m; ++i)
	{
		scanf("%lld", &x);
		vec(x).push_back(i);
	}
	for (int i = 1; i <= n; ++i)
	{
		scanf("%lld", &Q[i].w);
		Q[i].id = i;
	}
	scanf("%lld", &k);
	for (int i = 1; i <= k; ++i)	scanf("%lld %lld %lld", &qls[i], &qrs[i], &qva[i]);
	qls[++k] = 1, qrs[k] = n, qva[k] = 1e9;
	solve(1, k, 1, n);
	for (int i = 1; i <= n; ++i)
	{
		if (ans[i] == k)	puts("NIE");
		else	printf("%lld\n", ans[i]);
	}
	return 0;
}