Problem
Solution
Thinking 1
修改操作显然是区间加，可以整体二分。
但是如果这个区间按照国家来看的话，就不是连续的了，然道要\(n\log{n}\)单点修改？不必，反过来，把每个国家的基站存起来，询问时直接每个基站的贡献相加。
Thinking 2
每个基站的贡献可以用单点查询得到，BIT维护。
Thinking 3
然后变成了整体二分板子。
# include <bits/stdc++.h>
using namespace std;
# define int long long
const int N = 3e5 + 5;
int n,m,k;
vector <int> g[N];
int p[N];
int a[N],ans[N];
int lc[N],rc[N];
template <typename T> void read(T &x) {int w = 1;x = 0; char ch = getchar(); while(!isdigit(ch)) {if(ch == ‘-‘) w = -1; ch = getchar();} while(isdigit(ch)){x = x * 10 + ch - ‘0‘; ch = getchar();} x *= w;}
struct node
{
int l,r,a;
node() {}
node(int _l,int _r,int _a) : l(_l),r(_r),a(_a) {}
}A[N];
struct BIT
{
int T[N];
int lowbit(int x) {return x & (-x);}
void add(int x,int d)
{
while(x <= m)
{
T[x] += d,x += lowbit(x);
}
return;
}
int query(int x)
{
int total = 0;
while(x)
{
total += T[x];x -= lowbit(x);
}
return total;
}
void update(int l,int r,int d)
{
add(l,d),add(r + 1,-d);
return;
}
}T;
void dfs(int L,int R,int l,int r)
{
if(l > r) return;
// printf("L = %lld,R = %lld,l = %lld,r = %lld\n",L,R,l,r);
if(L == R)
{
for(int i = l; i <= r; i++) ans[a[i]] = L;
return;
}
int mid = (L + R) >> 1,lt = 0,rt = 0;
for(int i = L; i <= mid; i++)
{
if(A[i].l <= A[i].r) T.add(A[i].l,A[i].a),T.add(A[i].r + 1,-A[i].a);
else T.add(A[i].l,A[i].a),T.add(1,A[i].a),T.add(A[i].r + 1,-A[i].a);
// if(A[i].l <= A[i].r) T.update(A[i].l,A[i].r,A[i].a);
// else T.update(A[i].l,m,A[i].a),T.update(1,A[i].r,A[i].a);
}
for(int i = l; i <= r; i++)
{
int cur = 0;
for(int j = 0; j < (int)g[a[i]].size(); j++)
{
cur += T.query(g[a[i]][j]);
if(cur >= p[a[i]]) break;
}
if(cur >= p[a[i]]) lc[++lt] = a[i];
else rc[++rt] = a[i],p[a[i]] -= cur;
}
for(int i = L; i <= mid; i++)
{
if(A[i].l <= A[i].r) T.add(A[i].l,-A[i].a),T.add(A[i].r + 1,A[i].a);
else T.add(A[i].l,-A[i].a),T.add(1,-A[i].a),T.add(A[i].r + 1,A[i].a);
// if(A[i].l <= A[i].r) T.update(A[i].l,A[i].r,-A[i].a);
// else T.update(A[i].l,m + 1,A[i].a),T.update(1,A[i].r,-A[i].a);
}
for(int i = 1; i <= lt; i++) a[l + i - 1] = lc[i];
for(int i = 1; i <= rt; i++) a[l + lt + i - 1] = rc[i];
dfs(L,mid,l,l + lt - 1);
dfs(mid + 1,R,l + lt,r);
return;
}
signed main(void)
{
read(n),read(m);
for(int i = 1; i <= m; i++)
{
int x;
read(x);
g[x].push_back(i);
}
for(int i = 1; i <= n; i++)
{
read(p[i]);
a[i] = i;
}
read(k);
for(int i = 1; i <= k; i++)
{
int l,r,a;
read(l),read(r),read(a);
A[i] = node(l,r,a);
}
A[k + 1] = node(1,m,1e9 + 7);
dfs(1,k + 1,1,n);
for(int i = 1; i <= n; i++)
{
if(ans[i] > k) printf("NIE\n");
else printf("%lld\n",ans[i]);
}
return 0;
}