题解 CF1491A【K-th Largest Value】

RBI_GL · 2021-03-07 13:12:43 · 题解

题意

给出一个长度为 n 的 01 序列，并执行 q 次操作。操作有如下两种

• 将 a_x 的值 0 变 1，1 变 0。
  • 询问该序列中第 k 大的数。

思路

每次修改时更新数组中 1 和 0 的个数，查询时，如果 k 小于等于 1 的数量，则输出 1，否则输出 0。

Code:

#include <bits/stdc++.h>
using namespace std;
int n, q;
int a[100005];
int main() {
    cin >> n >> q;
    int one = 0, zero = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]); 
        if (a[i] == 1) one++;
        else zero++;
    }
    while(q--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) {
            if (a[x] == 0) {
                zero--, one++;
                a[x] = 1;
            }
            else {
                one--, zero++;
                a[x] = 0;
            }
        }
        else {
            if (x <= one) puts("1");
            else puts("0");
        }
    }
    return 0;
}