โค้ด C++ ประมวลผลคิวรีบนอาร์เรย์ไบนารี

สมมติว่าเรามีอาร์เรย์ A ขนาด n และรายการคิวรี Q จำนวน q คิวรี แต่ละ Query[i] มีคู่ (x, k) เวลาประมวลผลคิวรี สำหรับ x: ลดค่า A[x] ลง 1 สำหรับ k: พิมพ์ค่าที่ใหญ่ที่สุดลำดับที่ k เริ่มต้นทุกค่าใน A เป็น 0 หรือ 1

เช่น ถ้าอินพุตคือ A = [1, 1, 0, 1, 0]; Q = [[2, 3], [1, 2], [2, 3], [2, 1], [2, 5]] เอาต์พุตจะเป็น [1, 1, 1, 0]

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
m := 0
for i := 0 ถึง n-1:
    if A[i] non-zero: เพิ่ม m ขึ้น 1
for j := 0 ถึง size of Q - 1:
    x := Q[j, 0]
    k := Q[j, 1]
    if x == 0:
        if A[k] non-zero: ลด m ลง 1
        otherwise: เพิ่ม m ขึ้น 1
        A[k] := A[k] XOR 1
    otherwise:
        if m >= k: print 1
        otherwise: print 0

ตัวอย่างโค้ด

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

void solve(vector<int> A, vector<vector<int>> Q) {
    int n = A.size();
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (A[i]) m++;
    }
    for (int j = 0; j < Q.size(); j++) {
        int x = Q[j][0];
        int k = Q[j][1];
        if (x == 0) {
            if (A[k]) m--;
            else m++;
            A[k] ^= 1;
        } else {
            if (m >= k) cout << 1 << ", ";
            else cout << 0 << ", ";
        }
    }
}

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

อินพุต

{ 1, 1, 0, 1, 0 }, { { 1, 2 }, { 0, 1 }, { 1, 2 }, { 1, 0 }, { 1, 4 } }

เอาต์พุต

1, 1, 1, 0,