TIOJ 1919：王老先生

TIOJ 1919：王老先生

題目大意：有 $m$ 塊地，第 $i$ 塊屬於第 $a_i$ 個人，第 $i$ 個人想得到 $V_i$ 元，每次有一個區間
$[L_i, R_i]$，只要自己有地在這個區間裡，就可以拿 $C_i$ 元，問每個人在第幾個區間後就可以拿到自己想要的錢。 

解法：可以對區間們從 $1\sim Q+1$ 整體二分搜，每次二分搜時要處理 $l\sim mid$ 的區間，然後看第 $i$ 個人有沒有達成目標，若有，把他放到左邊那一組，若無，將 $V_i$ 扣掉 $l\sim mid$ 得到的錢，並放在右邊那一組。至於如何知道每個人得多少錢呢，可以將每個區間分成 $(L_i,L_i,C_i)$, $(R_i+1,L_i,-C_i)$，然後全部 $\text{push}$ 後排序，每次都用 $\text{BIT}$ 更新中間的 $L_i$ 的值，然後可以把需要用到的位置排序後來處理。可以用 $\text{last}$ 紀錄上一次出現的位置是哪裡。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define F first
#define S second
#define LL long long
#define pb emplace_back

const int SIZE = 1e5 + 5;

struct Ask {
    int l, r, c;
    Ask() {}
    Ask (int l, int r, int c) : l (l), r (r), c (c) {}
    bool operator < (const Ask &a) const {
        if (l!= a.l)
            return l < a.l;
        return r < a.r;
    }
} ask[SIZE];

int N, M, Q, qsiz;
int a[SIZE], V[SIZE], ans[SIZE];
int q[SIZE], q1[SIZE], q2[SIZE], last[SIZE];
LL bit[SIZE], sum[SIZE];
bool ok[SIZE];
vector<int> pos[SIZE];

void update (int p, int x) {
    for (; p <= M + 1; p += p & -p)
        bit[p] += x;
}

LL query (int p) {
    LL re = 0;
    for (; p; p -= p & -p)
        re += bit[p];
    return re;
}

void divide (int l, int r, int L, int R) {
    if (L > R)
        return;
    if (l == r) {
        FOR (i, L, R) ans[q[i]] = l;
        return;
    }
    int cnt1 = 0, cnt2 = 0, mid = (l + r) / 2, lp = 0;
    vector<Ask> p;
    vector<int> v;
    FOR (i, l, mid) {
        p.pb (ask[i].l, ask[i].l, ask[i].c);
        p.pb (ask[i].r + 1, ask[i].l, -ask[i].c);
    }
    FOR (i, L, R) {
        for (int x : pos[q[i]])
            v.pb (x);
    }
    sort (p.begin(), p.end());
    sort (v.begin(), v.end());
    for (int x : v) {
        while (lp < p.size() && p[lp].l <= x)
            update (p[lp].r, p[lp].c), lp++;
        sum[a[x]] += query (x) - query (last[a[x]]);
        last[a[x]] = x;
    }
    while (lp < p.size())
        update (p[lp].r, p[lp].c), lp++;
    FOR (i, L, R) {
        last[q[i]] = 0;
        if (sum[q[i]] >= V[q[i]])
            q1[++cnt1] = q[i];
        else {
            V[q[i]] -= sum[q[i]];
            q2[++cnt2] = q[i];
        }
        sum[q[i]] = 0;
    }
    FOR (i, 1, cnt1) q[L + i - 1] = q1[i];
    FOR (i, 1, cnt2) q[L + cnt1 + i - 1] = q2[i];
    divide (l, mid, L, L + cnt1 - 1);
    divide (mid + 1, r, L + cnt1, R);
}

void solve() {
    cin >> N >> M >> Q;
    FOR (i, 1, M) cin >> a[i], ok[a[i]] = 1, pos[a[i]].pb (i);
    FOR (i, 1, N) cin >> V[i];
    FOR (i, 1, Q) cin >> ask[i].l >> ask[i].r >> ask[i].c;
    FOR (i, 1, N) {
        if (V[i] == 0)
            ans[i] = 0;
        else if (!ok[i])
            ans[i] = -1;
        else
            q[++qsiz] = i;
    }
    divide (1, Q + 1, 1, qsiz);
    FOR (i, 1, N) cout << (ans[i] == Q + 1 ? -1 : ans[i]) << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！