Description

这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
输入：
第一行是两个数N,M。
第二行有M个数，第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数，第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K，表示BIU预测了接下来的K场陨石雨。
接下来K行，每行有三个数Li,Ri,Ai，表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中（如果Li<=Ri，就是Li,Li+1,...,Ri，否则就是Ri,Ri+1,...,m-1,m,1,...,Li），向区间中的每个太空站提供Ai单位的陨石样本。
输出：
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到，输出NIE。
数据范围：

Input

Output

Sample Input

Sample Output

首先这是一道权限题（xmcxmc？xmcxmc！）

蒟蒻在学习ZJOIday1T2的题解（%lych_cys初三进队爷)感觉好难理解，一定是我太弱了。

然后就找了一道分治的简单题。

这个方法也叫作整体二分。

首先对于1个国家的话，我们是可以二分答案的。

对于N个国家的话，就一起二分答案，那怎么二分呢。

solve(l,r,L,R) 表示 (l,r)是答案的可行区间，(L，R)是哪些国家的答案在这个可行区间内。

然后对于每次二分的答案 整体check，把可行的国家放入（l，mid）区间

不可行就放入（mid+1，r）区间 然后递归解决。

不过时间复杂度的分析并不怎么会，还是问lych_cys大神吧

#include <cstdio>
#include <cstring>
#define maxn 300010
#define ll long long
using namespace std;
struct cool
{
	int l,r,k;
}a[maxn];
int ans[maxn],c[maxn],al[maxn],ar[maxn],head[maxn],last[maxn],h[maxn],l,n,m,p[maxn];
ll g[maxn],cur[maxn];
void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}

ll query(int x)
{
	ll y = 0;
	for (;x;x -= x&-x)
		y += g[x];
	return y;
}
void update(int x,int y)
{
	for (;x <= m;x += x&-x)
		g[x] += y;
}
void Trans(int l,int r,int k)
{
	update(l,k);update(r+1,-k);
}

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[c[i]] = l;
		return;
	}
	int mid = (l+r)>>1;
	for (int i = l;i <= mid;i++)
		if (a[i].l > a[i].r)
			Trans(a[i].l,m,a[i].k),Trans(1,a[i].r,a[i].k);
		else Trans(a[i].l,a[i].r,a[i].k);
	int alen = 0,aren = 0;
	for (int j = L;j <= R;j++)
	{
		ll tmp = 0,i = c[j];
		for (int x = head[i];x;x = last[x])
		{
			tmp += query(h[x]);
			if (tmp+cur[i] > p[i]) break;
		}
		if (tmp+cur[i] >= p[i]) al[++alen] = i;
		else ar[++aren] = i,cur[i] += tmp;
	}
	for (int i = l;i <= mid;i++)
		if (a[i].l > a[i].r)
			Trans(a[i].l,m,-a[i].k),Trans(1,a[i].r,-a[i].k);
		else Trans(a[i].l,a[i].r,-a[i].k);
	for (int i = 1;i <= alen;i++) c[L+i-1] = al[i];
	for (int i = 1;i <= aren;i++) c[L+alen+i-1] = ar[i];
	solve(l,mid,L,L+alen-1);
	solve(mid+1,r,L+alen,R);
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i++)
	{
		int x;
		scanf("%d",&x);
		add(x,i);
	}
	for (int i = 1;i <= n;i++)
		scanf("%d",&p[i]),c[i] = i;
	int q;
	scanf("%d",&q);
	for (int i = 1;i <= q;i++)
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
	a[++q].l = 1;a[q].r = m;a[q].k = 2000000000;
	solve(1,q,1,n);
	for (int i = 1;i <= n;i++)
		if (ans[i] == q) puts("NIE");
		else printf("%d\n",ans[i]);
	return 0;
}