【整体二分+树状数组】Meteros

分治

传送门：CodeVS4232

似乎是POI的题（CV上各地的题有很多啊，然而似乎没更新近几年的。。。）

首先把环拆成链，然后给每个国家所在的太空站建一个链。

然后进行整体二分，把所有国家放在一个集合里，然后对场数（即答案）进行二分，判断在这个场数内能否达标，达标则放入一个集合，不达标放入另一个，分治一下。

那么问题就转化为了统计各个国家有没有达标，用树状数组维护区间和，然后单点（实际是多点，多个空间站）查询。

然而开始写完T的一塌糊涂（说实话这数据真良心，34个点），然后发现我把空间站放在集合里，重复了好几次，然后改了还是T。估计是因为N与M同阶，差的不多，然后发现我用链来写集合，与别人似乎都不大一样，而且我是用一个指针来控制修（乱）改（搞）树状数组的范围的，似乎会重复（然而我并不觉得），反正就是常数大，最后加了胡乱剪枝（没错分治用剪枝）才卡过（刺激啊！！！）

至于怎么优化常数，还是以后再想吧（智力孤危）

以下代码（T了别怪我）

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
LL n,m,p,tot,ans,T;
LL l[300030],r[300030],c[300030],head[300030],f[300030];
LL a[600030],b[600030],nxt[600030],bit[600030];
struct edge{
	LL v,next;
}e[600030];
void add(LL x,LL y){
	tot++;
	e[tot].v=y;
	e[tot].next=head[x];
	head[x]=tot;
}
bool query(LL x,LL y){
	LL sum=0;
	for (int i=head[x];i;i=e[i].next){
		for (int j=e[i].v;j;j-=j&(-j))
			sum+=bit[j];
		if (sum>=y) break;
	}
	return sum>=y;
}
void ins(LL x,LL y){
	if (r[x]<l[x]) r[x]+=m;
	for (int i=l[x];i<=m*2-1;i+=i&(-i))
		bit[i]+=c[x]*y;
	for (int i=r[x]+1;i<=m*2-1;i+=i&(-i))
		bit[i]-=c[x]*y;
}
void work(LL l,LL r,LL s){
	if (s==0) return;
	LL mid=(l+r)>>1;
	while(T<mid){
		T++;
		ins(T,1);
	}
	while(T>mid){
		ins(T,-1);
		T--;
	}
	
	LL h1=0,h2=0,j=0;
	for (int i=s;i;i=j){
		j=nxt[i];
		if (query(i,b[i]))
			nxt[i]=h2,h2=i;
		else
			nxt[i]=h1,h1=i;
	}
	
	if (l==r){
		for (int i=h2;i;i=nxt[i])
			f[i]=l;
		return;
	}
	work(mid+1,r,h1);
	work(l,mid,h2);
}
		
int main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%lld",&a[i]);
		add(a[i],i);
	}
	for (int i=m+1;i<m*2;i++){
		a[i]=a[i-m];
		add(a[i],i);
	}
	for (int i=1;i<=n;i++) scanf("%lld",&b[i]);
	scanf("%lld",&p);
	for (int i=1;i<=p;i++) scanf("%lld%lld%lld",&l[i],&r[i],&c[i]);
	
	for (int i=n;i;i--) nxt[i]=i-1;
	
	work(1,p,n);
	
	for (int i=1;i<=n;i++)
		if (f[i]==0) printf("NIE\n");
		else printf("%lld\n",f[i]);
	
	return 0;
}