3240 : 회원 참여도 분석1

//회원 참여도
//생각할 문제
//참여도가 가장 높은 회원과 가장 낮은 회원을 빠른 시간에 찾아내야 한다.
//쿼리가 있을 때마다 순차 탐색을 하면 O(N^2)으로 시간 초과
//이진 탐색을 하기 위해서는 자료 추가 및 제거마다 정렬을 해야 하므로 역시 의미가 없다.
//힙(heap): 완전 이진트리를 이용하여 부모가 항상 크거나(max heap) 항상 작도록(min heap) 자료를 구성하면 최대값 또는 최소값이 항상 루트에 위치하게 된다.
//인덱스트리 or 세그먼트 트리 : 이진트리로 특정 구간의 자식 중 큰 값(max tree)또는 작은값(min tree)을 넣어서 루트에 최대값 또는 최소값이 위치하도록 구성되는 자료 구조
//힙이나 인덱스 트리 등 모두 부모만 따라서 갱신하면 되므로 자료를 추가 또는 삭제할 때 갱신하는 시간은 O(logN)이 된다.

//인덱스 트리를 이용한 풀이
// - 트리에서 ID별 시작위치 : 10만 이상인 2의 제곱수 -2^17

// 트리의 크기 : 2^18

// 트리의 구조 : 구조체로 sum, cnt, id, frequence를 저장하는 방법
// - sum과 cnt는 별도 관리하고 , id, frequence를 저장하는 방법
// - id별 frequence도 별도로 저장하고 트리에는 id만 저장하는 방법


// - 초기값 설정 및 추가 삭제 : MIN_ID와 MAX_ID를 10만 이상의 id로 설정하고 각각 최대값, 최소값을 저장한다.
// -  트리의 값을 MIN_ID와 MAX_ID로 초기화 하고
// - 자료가 추가될 때 해당 id를 넣고 삭제 할 때는 다시 MIN_ID와 MAX_ID로 바꾼 후 업데이트 한다.

#include 
#define ID (S + id)
const int S = 1 << 17;
const int MIN_ID = S - 2, MAX_ID = S - 1;
int N, M, arr[S], sum, cnt;

struct Tree {
int minid, maxid;

Tree() { minid = MIN_ID, maxid = MAX_ID; }
Tree(int id) { minid = maxid = id; }

bool operator<(const Tree &r) const {
if (arr[minid] != arr[r.minid]) return arr[minid] < arr[r.minid];
return minid < r.minid;
}
bool operator>(const Tree &r) const {
if (arr[maxid] != arr[r.maxid]) return arr[maxid] > arr[r.maxid];
return maxid > r.maxid;
}
}tree[S*2];

void update(int node) {
if (node < 1)return;
tree[node].minid = (tree[node * 2] < tree[node * 2 + 1]) ?
tree[node * 2].minid : tree[node * 2 + 1].minid;
tree[node].maxid = (tree[node * 2] > tree[node * 2 + 1]) ?
tree[node * 2].maxid : tree[node * 2 + 1].maxid;
update(node / 2);
}

void init() {
scanf("%d %d", &N, &M);
arr[MIN_ID] = S;
arr[MAX_ID] = -1;
}

int main() {
int cmd, id, fr;
init();
while (M--) {
scanf("%d", &cmd);
if (cmd == 0) {
scanf("%d %d", &id, &fr);
arr[id] = fr;
sum += fr;
cnt++;
tree[ID] = Tree(id);
update(ID / 2);
}
else if (cmd == 1 || cmd == 2) {
if (cnt <= 0) continue;
id = (cmd == 1) ? tree[1].minid : tree[1].maxid;
tree[ID] = Tree();
sum -= arr[id];
cnt--;
update(ID / 2);
printf("%d\n", id);
}
else {
if (cnt <= 2) printf("0\n");
else printf("%d\n", sum - arr[tree[1].maxid] - arr[tree[1].minid]);
}
}
return 0;
}