Nhận xét rằng, nếu số cổ phiếu của một cổ đông là hằng số ~c~ trong quá trình công ty thu về các cổ tức thì số tiền mà cổ đông thu về sẽ là ~c \times \text{(tổng giá trị cổ tức)}~. Do đó, với mỗi cổ đông, ta chỉ cần cập nhật tổng lợi nhuận mỗi khi số cổ phiếu của cổ đông có thay đổi (truy vấn loại ~1~) hoặc khi cần cho biết lợi nhuận hiện tại của cổ đông (truy vấn loại ~3~).

Về chi tiết cài đặt, ta cần lưu lại các giá trị sau:

• acc_profit[p]: Tổng lợi nhuận chưa được rút của cổ đông ~p~.
• stock_cnt[p]: Số cổ phiếu hiện tại của cổ đông ~p~.
• stock_price_index[p]: Tổng cổ tức công ty thu về được tính đến lần cập nhật cuối cùng của cổ đông ~p~.
• acc_stock_price: Tổng cổ tức cho đến truy vấn hiện tại.

Khi đó, với mỗi truy vấn ~1~ hoặc ~3~, ta cần cập nhật tổng lợi nhuận cho cổ đông ~p~ thêm một lượng bằng ~\texttt{stock_cnt[p]} \times (\texttt{acc_stock_price} - \texttt{stock_price_index[p]})~, rồi cập nhật lại các biến stock_cnt[p] và stock_price_index[p] một cách tương ứng.

Độ phức tạp: ~O(n + q)~

#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;
const u64 MOD = 1'000'000'007;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<u64> stock_cnt(n), acc_profit(n), stock_price_index(n);
    u64 acc_stock_price = 0;

    auto realize_profit = [&](int p) {
        u64 stock_price = (acc_stock_price - stock_price_index[p]) % MOD;
        stock_price_index[p] = acc_stock_price;

        acc_profit[p] += stock_cnt[p] % MOD * stock_price % MOD;
        acc_profit[p] %= MOD;
    };

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, x;
            cin >> p >> x;
            --p;
            realize_profit(p);
            stock_cnt[p] += x;
        } else if (t == 2) {
            int v;
            cin >> v;
            acc_stock_price += v;
        } else if (t == 3) {
            int p;
            cin >> p;
            --p;
            realize_profit(p);
            cout << exchange(acc_profit[p], 0) << '\n';
        }
    }

    return 0;
}