NKOJ 3932 Meteors （整体二分+树状数组）

发表于 |
字数统计: 1,147字 | 阅读时长 ≈ 5min

​

P3932Meteors

问题描述

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。

这个星球经常会下陨石雨。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。

样例输入

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

样例输出

3
NIE
1

提示

1<=n,m,k<=3*10^5 1<=Pi<=10^9 1<=Ai<10^9

如果只有一个国家，那么显然的二分答案，复杂度$O(m\log k+k\log m)$，用线段树或树状差分数组来维护每个太空站的情况，每次二分后只把两次二分区间的差的区间信息进行修改，最多修改k次。

考虑多个国家的情况，仍然暴力枚举每个国家的话，复杂度是$O(m\log k+nk\log m)$，考虑优化，这时注意到枚举每个国家时要维护的线段树其实是一样的，而主要的时间花费恰好是维护这个线段树，因此可以考虑整体二分，同样二分答案，每次判断每个国家的答案区间，将答案区间在$[l,mid]$的国家甩到$Q_1$里面，把答案区间在$[mid+1,r]$的甩到$Q_2$中，对$Q_1$递归求解，同时回溯的时候还原线段树，然后对$Q_2$递归求解，在底层的时候就算出了答案。这样就只需要维护全局线段树，而不需要每次二分答案都重新维护线段树。

总时间复杂度$O(m\log k \log m+k\log k\log m)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 400005
#define ll long long
using namespace std;
struct node
{
	ll v;
	vector<ll>p;
}C[N];
ll cur,id[N],Q1[N],Q2[N],n,m,q,L[N],R[N],A[N],D[N],Ans[N];
void MD(ll x,ll d)
{for(ll i=x;i<=m;i+=(i&-i))D[i]+=d;}
ll GS(ll x)
{
	ll i,sum=0;
	for(i=x;i;i-=(i&-i))sum+=D[i];
	return sum;
}
void CA(ll k,ll ty)
{
	if(L[k]<=R[k])MD(L[k],A[k]*ty),MD(R[k]+1,-A[k]*ty);
	else MD(L[k],A[k]*ty),MD(1,A[k]*ty),MD(R[k]+1,-A[k]*ty);
}
void Solve(ll l,ll r,ll sl,ll sr)
{
	ll i,j,k,x,y,mid=sl+sr>>1;
	if(sl==sr)
	{
		for(i=l;i<=r;i++)if(Ans[id[i]]!=-1)Ans[id[i]]=sl;
		return;
	}
	while(cur<mid)CA(++cur,1);
	while(cur>mid)CA(cur--,-1);
	x=y=0;
	for(i=l;i<=r;i++)
	{
		k=0;
		for(j=0;j<C[id[i]].p.size();j++)
		{
			k+=GS(C[id[i]].p[j]);
			if(k>=C[id[i]].v)break;
		}
		if(k>=C[id[i]].v)Q1[++x]=id[i];
		else Q2[++y]=id[i];
	}
	for(i=1;i<=x;i++)id[l+i-1]=Q1[i];
	for(i=1;i<=y;i++)id[r-i+1]=Q2[y-i+1];
	Solve(l,r-y,sl,mid);
	Solve(l+x,r,mid+1,sr);
}
int main()
{
	ll i,j,k,x,y,z;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%lld",&x);
		C[x].p.push_back(i);
	}
	for(i=1;i<=n;i++)scanf("%lld",&C[i].v),id[i]=i;
	scanf("%lld",&q);
	for(i=1;i<=q;i++)scanf("%lld%lld%lld",&L[i],&R[i],&A[i]);
	Solve(1,n,1,q+1);
	for(i=1;i<=n;i++)
	if(Ans[i]==q+1)puts("NIE");
	else printf("%lld\n",Ans[i]);
}