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

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

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

using namespace std;

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

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

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

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

void change(ll p , ll l , ll r ,ll 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;
	}
	ll 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 + t[p].add * (t[p].r - t[p].l + 1);
}

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

void solve(ll l , ll r , queue<ll>country){ // l , r 为答案范围 , country : 当前范围中国家 
	if(country.empty()){
		return;
	}
	if(l == r){
		while(!country.empty()){
			ans[country.front()] = l;
			country.pop();
		}
		return;
	}
	ll mid = (l + r) / 2;
	for(ll 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<ll> q_l , q_r;
	while(!country.empty()){
		ll now = country.front();
		country.pop();
		ll tot = 0;
		for(ll i = 0;i < belong[now].size() && tot < need[now];i++){
			tot += ask(1 , belong[now][i] , belong[now][i] , 0);
		}
		if(tot >= need[now]){
			q_l.push(now);
		}
		else{
			need[now] -= tot;
			q_r.push(now);
		}
	}
	for(ll 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(ll i = 1;i <= m;i++){
		ll x;
		cin >> x;
		belong[x].push_back(i);
	}
	for(ll i = 1;i <= n;i++){
		ll x;
		cin >> x;
		need[i] = x;
	}
	cin >> ys;
	for(ll i = 1;i <= ys;i++){
		ll 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<ll> country;
	for(ll i = 1;i <= n;i++){
		country.push(i);
	}
	solve(1 , ys + 1 , country);
	for(ll i = 1;i <= n;i++){
		if(ans[i] <= ys){
			cout << ans[i] << endl;
		}
		else{
			cout << "NIE" << endl;
		}
	}
	return 0;
}