Xử lý truy vấn trên mảng nhị phân: cập nhật và truy vấn k-th lớn nhất bằng C++

Mô tả bài toán

Mảng A n phần tử 0/1. Q truy vấn: mỗi truy vấn (x,k). Nếu x=0: đảo bit A[k]. Nếu x=1: in k-th largest element (1 là lớn nhất).

Ví dụ

A=[1,1,0,1,0], Q=[[1,2],[0,1],[1,2],[1,0],[1,4]] → Output: 1,1,1,0.

Thuật toán

Giữ biến m = số phần tử 1. Với x=0: flip A[k], cập nhật m. Với x=1: nếu m ≥ k thì in 1 else 0.

Code C++

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

void solve(vector A, vector> Q) {
    int m = 0;
    for (int x : A) if (x) m++;
    for (auto &q : Q) {
        int x = q[0], k = q[1];
        if (x == 0) {
            if (A[k]) m--;
            else m++;
            A[k] ^= 1;
        } else {
            cout << (m >= k ? 1 : 0) << ", ";
        }
    }
}

int main() {
    vector A = {1,1,0,1,0};
    vector> Q = {{1,2},{0,1},{1,2},{1,0},{1,4}};
    solve(A, Q);
    return 0;
}

Đầu vào / Đầu ra

Input: {1,1,0,1,0}, {{1,2},{0,1},{1,2},{1,0},{1,4}}

Output: 1, 1, 1, 0,