#54511: C++ 解答


kita197 (KK)


//使用GPT
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<int> X(N), Y(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i] >> B[i];
    }

    // 每顆恆星可見的星星
    vector<bitset<300>> visible(N);

    auto dist2 = [&](int i, int j) {
        long long dx = X[i] - X[j], dy = Y[i] - Y[j];
        return dx*dx + dy*dy;
    };

    // 初始化可見集合
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (dist2(i,j) <= 1LL*B[i]*B[i]) visible[i].set(j);
        }
    }

    // 預計算每個三元組可見星星數的頻率表
    vector<long long> freq(N+1, 0);
    for (int i = 0; i < N; i++)
    for (int j = i+1; j < N; j++)
    for (int k = j+1; k < N; k++) {
        int cnt = (visible[i] & visible[j] & visible[k]).count();
        freq[cnt]++;
    }

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int K;
            cin >> K;
            cout << freq[K] << "\n";
        } else {
            int Xid, C;
            cin >> Xid >> C;
            Xid--; // 0-indexed

            // 保存舊的 visible[Xid]
            bitset<300> old_vis = visible[Xid];

            // 更新 B[Xid] 並重新計算 visible[Xid]
            B[Xid] = C;
            visible[Xid].reset();
            for (int j = 0; j < N; j++) {
                if (dist2(Xid,j) <= 1LL*B[Xid]*B[Xid])
                    visible[Xid].set(j);
            }

            // 更新 freq:只處理包含 Xid 的三元組
            for (int i = 0; i < N; i++) {
                if (i == Xid) continue;
                for (int j = i+1; j < N; j++) {
                    if (j == Xid) continue;
                    int a = Xid, b = i, c = j;

                    // 舊的交集
                    int old_cnt = (old_vis & visible[b] & visible[c]).count();
                    // 新的交集
                    int new_cnt = (visible[a] & visible[b] & visible[c]).count();

                    freq[old_cnt]--;
                    freq[new_cnt]++;
                }
            }
        }
    }

    return 0;
}