POI的题时限都好紧……
学习了一波整体二分。
首先对于每一个询问我们可以分别二分求解，那么我们可以对所有的询问一起二分，在二分的时候可以减少答案的规模，因为每一次询问都可以划分到不同的答案区间中，当最后二分到$l == r$的时候就得到了答案。
对于这道题我们可以先找到一个$mid$，然后执行$[l, mid]$区间中的操作，就可以把所有的询问分组。
然后就是常数优化：
1、在累加答案的时候超过了目标直接$break$，要不然有爆$long long$的危险。
2、树状数组的常数很重要，写成差分形式的比较快。
时间复杂度$O(nlog^2n)$。
Code：
#include <cstdio> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int N = 3e5 + 5; const ll inf = 1LL << 60; int n, m, k; ll ans[N]; vector <int> vec[N]; struct Item { int l, r; ll val; } a[N]; struct Querys { int id; ll cur; } q[N], tmp[N]; /*template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } */ namespace IOread{ const int L = 1 << 15; char buffer[L], *S, *T; inline char Getchar() { if(S == T) { T = (S = buffer) + fread(buffer, 1, L, stdin); if(S == T) return EOF; } return *S++; } template <class T> inline void read(T &X) { char ch; T op = 1; for(ch = Getchar(); ch > '9' || ch < '0'; ch = Getchar()) if(ch == '-') op = -1; for(X = 0; ch >= '0' && ch <= '9'; ch = Getchar()) X = (X << 1) + (X << 3) + ch - '0'; X *= op; } } using namespace IOread; namespace Bit { ll s1[N], s2[N]; #define lowbit(p) (p & (-p)) inline void modify(int p, ll v) { for(int i = p; i <= m; i += lowbit(i)) s1[i] += v, s2[i] += 1LL * p * v; } inline ll query(int p) { ll res = 0LL; for(int i = p; i > 0; i -= lowbit(i)) res += 1LL * (p + 1) * s1[i] - s2[i]; return res; } inline void modifySeg(int l, int r, ll v) { if(l > r) { modify(l, v); modify(1, v), modify(r + 1, -v); } else modify(l, v), modify(r + 1, -v); } inline ll querySeg(int l, int r) { return query(r) - query(l - 1); } } using namespace Bit; /*namespace SegT { ll s[N << 2], tag[N << 2]; #define lc p << 1 #define rc p << 1 | 1 #define mid ((l + r) >> 1) inline void up(int p) { s[p] = s[lc] + s[rc]; } inline void down(int p, int l, int r) { if(!tag[p]) return; s[lc] += 1LL * (mid - l + 1) * tag[p]; s[rc] += 1LL * (r - mid) * tag[p]; tag[lc] += tag[p], tag[rc] += tag[p]; tag[p] = 0LL; } void modify(int p, int l, int r, int x, int y, ll v) { if(x <= l && y >= r) { s[p] += 1LL * (r - l + 1) * v; tag[p] += v; return; } down(p, l, r); if(x <= mid) modify(lc, l, mid, x, y, v); if(y > mid) modify(rc, mid + 1, r, x, y, v); up(p); } ll query(int p, int l, int r, int x) { if(l == r) return s[p]; down(p, l, r); if(x <= mid) return query(lc, l, mid, x); else return query(rc, mid + 1, r, x); } inline void modifySeg(int l, int r, ll v) { if(l > r) { modify(1, 1, m, l, m, v); modify(1, 1, m, 1, r, v); } else modify(1, 1, m, l, r, v); } #undef mid } using namespace SegT; */ void solve(int l, int r, int ql, int qr) { if(ql > qr) return; if(l == r) { for(int i = ql; i <= qr; i++) ans[q[i].id] = l; return; } int mid = (l + r) / 2; for(int i = l; i <= mid; i++) modifySeg(a[i].l, a[i].r, a[i].val); int nowl = ql - 1, nowr = qr + 1; for(int i = ql; i <= qr; i++) { int vecSiz = vec[q[i].id].size(); ll now = 0LL; for(int j = 0; j < vecSiz; j++) { int pos = vec[q[i].id][j]; // now += query(1, 1, m, pos); now += querySeg(pos, pos); if(now >= q[i].cur) break; } if(now >= q[i].cur) tmp[++nowl] = q[i]; else { q[i].cur -= now; tmp[--nowr] = q[i]; } } for(int i = ql; i <= nowl; i++) q[i] = tmp[i]; for(int i = nowr; i <= qr; i++) q[i] = tmp[i]; for(int i = l; i <= mid; i++) modifySeg(a[i].l, a[i].r, -a[i].val); solve(l, mid, ql, nowl); solve(mid + 1, r, nowr, qr); } int main() { // freopen("met82.in", "r", stdin); // freopen("my.out", "w", stdout); read(n), read(m); for(int pos, i = 1; i <= m; i++) { read(pos); vec[pos].push_back(i); } for(int i = 1; i <= n; i++) { read(q[i].cur); q[i].id = i; } read(k); for(int i = 1; i <= k; i++) read(a[i].l), read(a[i].r), read(a[i].val); a[++k] = (Item) {1, m, inf}; solve(1, k, 1, n); for(int i = 1; i <= n; i++) { if(ans[i] == k) puts("NIE"); else printf("%lld ", ans[i]); } return 0; }