记录编号	573147	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAATAAAAATAA
题目名称	2714.[POI 2011]流星	最终得分	94
用户昵称	湖岸与夜与咸鱼	是否通过	未通过
代码语言	C++	运行时间	18.715 s
提交时间	2022-07-18 19:18:49	内存使用	41.54 MiB

// 河南省实验中学 21届 关天泽

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;

struct Segmenttree{
	ll add , w; // w 当前区间陨石数 
	int l , r;
};

struct Meteors{ //陨石雨数据 
	ll k; // 陨石数量 
	int l , r; //陨石雨区间 
	bool opt; // 0 为 l - r , 1 为 r - m - 1 - l 
};

Segmenttree t[1200050];
ll need[300050]; // 国家需要陨石数量 
Meteors que[300050];
vector<int> belong[300050]; // 各国空间站 
int n , m , ans[300050] , ys; // ys : 陨石雨数量 

void build(int p , int l , int r){
	t[p].l = l;
	t[p].r = r;
	t[p].w = 0;
	if(l == r){
		return;
	}
	int mid = (l + r) / 2;
	build(2 * p , l , mid);
	build(2 * p + 1 , mid + 1 , r);
	return;
}

void spread(int p){
	if(t[p].add != 0){
		t[2 * p].w += t[p].add * (t[p * 2].r - t[p * 2].l + 1);
		t[2 * p + 1].w += t[p].add * (t[p * 2 + 1].r - t[p * 2 + 1].l + 1);
		t[2 * p].add += t[p].add;
		t[2 * p + 1].add += t[p].add;
		t[p].add = 0;
	}
}

void change(int p , int l , int r ,int d){
	if(l <= t[p].l && r >= t[p].r){
		t[p].w += d * (t[p].r - t[p].l + 1);
		t[p].add += d;
		return;
	}
	spread(p);
	int mid = (t[p].r + t[p].l) / 2;
	if(l<= mid){
		change(p * 2 , l , r , d);
	}
	if(r > mid){
		change(p * 2 + 1, l , r , d);
	}
	t[p].w = t[2 * p].w + t[2 * p + 1].w;
}

ll ask(int p , int l , int r){
	if(l <= t[p].l && r >= t[p].r){
		return t[p].w;
	}
	spread(p);
	int mid = (t[p].l + t[p].r) / 2;
	ll val = 0;
	if(l <= mid){
		val += ask(2 * p , l , r);
	}
	if(r > mid){
		val += ask(2 * p + 1 , l , r);
	}
	return val;
}

void solve(int l , int r , queue<int>country){ // l , r 为答案范围 , country : 当前范围中国家 
	if(country.empty()){
		return;
	}
	if(l == r){
		while(!country.empty()){
			ans[country.front()] = l;
			country.pop();
		}
		return;
	}
	int mid = (l + r) / 2;
	for(int i = l;i <= mid;i++){
		if(!que[i].opt){
			change(1 , que[i].l , que[i].r , que[i].k);
		}
		if(que[i].opt){
			change(1 , que[i].l , m , que[i].k);
			change(1 , 1 , que[i].r , que[i].k);
		}
	}
	queue<int> q_l , q_r;
	while(!country.empty()){
		int now = country.front();
		country.pop();
		ll tot = 0;
		for(int i = 0;i < belong[now].size() && tot < need[now];i++){
			tot += ask(1 , belong[now][i] , belong[now][i]);
		}
		if(tot >= need[now]){
			q_l.push(now);
		}
		else{
			need[now] -= tot;
			q_r.push(now);
		}
	}
	for(int i = l;i <= mid;i++){
		if(!que[i].opt){
			change(1 , que[i].l , que[i].r , -que[i].k);
		}
		if(que[i].opt){
			change(1 , que[i].l , m , -que[i].k);
			change(1 , 1 , que[i].r , -que[i].k);
		}
	}
	if(!q_l.empty()){
		solve(l , mid , q_l);
	}
	if(!q_r.empty()){
		solve(mid + 1 , r , q_r);
	}
	return;
}

int main(){
	freopen("meteors.in" , "r" , stdin);
	freopen("meteors.out" , "w" , stdout);
	cin >> n >> m;
	build(1 , 1 , m);
	for(int i = 1;i <= m;i++){
		int x;
		cin >> x;
		belong[x].push_back(i);
	}
	for(int i = 1;i <= n;i++){
		int x;
		cin >> x;
		need[i] = x;
	}
	cin >> ys;
	for(int i = 1;i <= ys;i++){
		int x , y , z;
		cin >> x >> y >> z;
		que[i].k = z;
		que[i].l = x;
		que[i].r = y;
		if(y >= x){
			que[i].opt = 0;
		}
		else{
			que[i].opt = 1;
		}
	}
	queue<int> country;
	for(int i = 1;i <= n;i++){
		country.push(i);
	}
	solve(1 , ys + 1 , country);
	for(int i = 1;i <= n;i++){
		if(ans[i] <= ys){
			cout << ans[i] << endl;
		}
		else{
			cout << "NIE" << endl;
		}
	}
	return 0;
}