传送门

其实整体二分就是在二分答案的同时把询问也二分了。排除询问不可能的值域。

树状数组可以区间更新单点查询，不要傻傻地去写区间更新区间查询的树桩上数组。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
int o[maxn], b[maxn], lb[maxn], rb[maxn];
vector<int> pos[maxn];
ll p[maxn];
int ans[maxn];
int n, m, k;
struct rec{
    int l, r; ll v;
}a[maxn];
ll c[2][maxn];
void add(int t, int x, ll v)
{
    for(; x <= m; x += x & -x) c[t][x] += v;
}
ll ask(int t, int x)
{
    ll res = 0;
    for(; x; x -= x & -x) res += c[t][x];
    return res;
}
void update(int l, int r, ll v)
{
    // cout << l << "+" << r << endl;
    if(l <= r)
    {
        add(0, l, v);
        add(0, r + 1, -v);
        //add(1, l, l * v);
        //add(1, r + 1, -(r + 1) * v);
    }
    else 
    {
        int ll = r, rr = l;
        l = 1, r = ll;
        add(0, l, v);
        add(0, r + 1, -v);
        //add(1, l, l * v);
        //add(1, r + 1, -(r + 1) * v);
        l = rr, r = m;
        add(0, l, v);
        add(0, r + 1, -v);
        //add(1, l, l * v);
        //add(1, r + 1, -(r + 1) * v);
    }
}
ll query(int l, int r)
{
    // cout << l << ' ' << r << endl;
    if(l <= r)
    {
        ll res = (ll)(r + 1) * ask(0, r) - ask(1, r);
        res -= (ll)l * ask(0, l - 1) - ask(1, l - 1);
        return res;
    }
    else 
    {
        ll res = 0;
        ll ll = r, rr = l;
        l = 1, r = ll;
        res += (r + 1) * ask(0, r) - ask(1, r);
        res -= l * ask(0, l - 1) - ask(1, l - 1);
        l = rr, r = m;
        res += (r + 1) * ask(0, r) - ask(1, r);
        res -= l * ask(0, l - 1) - ask(1, l - 1);
        return res;
    }

}
ll now[maxn];
void solve(int lv, int rv, int st, int ed)
{
    if(st > ed) return;
    if(lv == rv) 
    {
        for(int i = st; i <= ed; i++) ans[b[i]] = lv;
        return;
    }
    int mid = (lv + rv) >> 1;
    int lt = 0, rt = 0;
    for(int i = lv; i <= mid; i++) update(a[i].l, a[i].r, a[i].v);
    //cout << query(1, 5) << "?" << endl;
    for(int i = st; i <= ed; i++)
    {
        ll cnt = 0;
        for(int j = 0; j < pos[b[i]].size(); j++) 
        {
            //cnt += query(pos[b[i]][j], pos[b[i]][j]);
            cnt += ask(0, pos[b[i]][j]);
            if(cnt >= p[b[i]]) break;
        }
        now[b[i]] = cnt;
    }
    for(int i = st; i <= ed; i++)
    {
        if(now[b[i]] >= p[b[i]]) lb[++lt] = b[i];
        else p[b[i]] -= now[b[i]], rb[++rt] = b[i];
    }
    for(int i = lv; i <= mid; i++) update(a[i].l, a[i].r, -a[i].v);
    for(int i = 1; i <= lt; i++) b[i + st - 1] = lb[i];
    for(int i = 1; i <= rt; i++) b[i + lt + st - 1] = rb[i];
    solve(lv, mid, st, st + lt - 1);
    solve(mid + 1, rv, st + lt, ed);
}
int main()
{
    memset(ans, -1, sizeof ans);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) scanf("%d", &o[i]), pos[o[i]].push_back(i);
    for(int i = 1; i <= n; i++) scanf("%lld", &p[i]), b[i] = i;
    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%d%d%lld", &a[i].l, &a[i].r, &a[i].v);
    a[++k] = {1, m, 0};
    solve(1, k, 1, n);
    for(int i = 1; i <= n; i++)
        if(ans[i] != k) printf("%d\n", ans[i]);
        else printf("NIE\n");
}