Codeforces #1491A K-th Largest Value

문제

https://codeforces.com/problemset/problem/1491/A

걸린 시간

00 : 12 : 44

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] == 1) cnt++;
    }
    int t, x;
    for(int i = 0; i < q; i++){
        cin >> t >> x;
        if(t == 1){
            if(a[x-1] == 1) cnt--;
            else cnt++;
            a[x-1] = 1-a[x-1];
        }
        else{
            if(x <= cnt) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
    }
    return 0;
}

0 과 1 로만 구성된 배열 a 와 두가지 종류가 있는 쿼리 q 개가 주어진다.

첫번째 쿼리는 해당 인덱스의 비트(0,1)를 반전시키는 역할, 두번째 쿼리는 비오름차순(중복된 값을 허용하는 내림차순) 으로 정렬된 배열 a 에서 k 번째로 큰 수를 출력한다.

해결방법은 배열 a 에 존재하는 1의 개수를 첫번째 쿼리가 들어올 때 마다 갱신해주고 두번째 쿼리가 들어오면 1의 개수와 k 값을 비교하여 1 또는 0 을 출력해준다.