BOJ)11338 XOR Sum

문제: icpc.me/11338

n개의 쿼리가 주어질 때 2가지 쿼리에 따라서 문제를 해결하는 문제이다.

insert 쿼리는 리스트에 숫자를 추가하는것이며 

print 쿼리는 리스트 중에 상위 K숫자를 XOR한 값을 출력하는 문제이다.

우리는 매 print마다 리스트에서 XOR을 할 경우 시간초과가 나므로 insert 될 때 마다 모든 값을 XOR해준 뒤 minheap을 이용하여 리스트 숫자가 K를 초과할때 마다 최솟값을 XOR해준다. 이는 A^X^X=A가 되는 원리를 이용하는 풀이이다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
char a[7];
int t, m, k, n, r, c;
int main() {
    scanf("%d", &t);
    while (t--) {
        r = c = 0;
        priority_queue<int> pq;
        scanf("%d%d", &m, &k);
        for (int i = 0; i < m; i++) {
            scanf("%s", &a);
            if (a[0] == 'i') {
                scanf("%d", &n);
                pq.push(-n);
                r ^= n;
                c++;
                if (c > k) {
                    r ^= -pq.top();
                    pq.pop();
                }
                    
            }
            else {
                printf("%d\n", r);
            }
        }
    }
    return 0;
}