# 11990: 【原1990】二哥听CD

### 题目描述

author: qujun 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1990

## 样例输入

3 4
1 2 3
1 1
1 1
2 1
3 －1


## 样例输出

1
2
2
3


## Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 2e6 + 100;

struct Node {
int id;
int like;
int date;
};

int pos[maxN] = {0}, N, M, date = 1;
Node heap[maxN] = {0};

void buildHeap();
void percolateUp(int);
void percolateDown(int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> heap[i].like;
heap[i].id = i;
heap[i].date = date++;
pos[i] = i;
}

buildHeap();

int x, y;
for (int i = 0; i < M; i++) {
cin >> x >> y;
heap[pos[x]].like += y;
heap[pos[x]].date = date++;
if (y > 0) {
percolateDown(pos[x]);
} else if (y < 0) {
percolateUp(pos[x]);
}
cout << heap[1].id << '\n';
}

return 0;
}

void buildHeap() {
for (int i = N / 2; i > 0; i--) {
percolateDown(i);
}
}

void percolateUp(int hole) {
int like = heap[hole].like, id = heap[hole].id, date = heap[hole].date,
parent;

while (hole / 2 != 0) {
parent = hole / 2;
if (like <= heap[parent].like) {
heap[hole].like = heap[parent].like;
heap[hole].id = heap[parent].id;
heap[hole].date = heap[hole].date;
pos[heap[hole].id] = hole;
hole = parent;
} else {
break;
}
}
heap[hole].id = id;
heap[hole].like = like;
heap[hole].date = date;
pos[id] = hole;
}

void percolateDown(int hole) {
int like = heap[hole].like, id = heap[hole].id, data = heap[hole].date,
child;

while ((hole * 2) <= N) {
child = hole * 2;
if (child < N) {
if (heap[child + 1].like < heap[child].like ||
(heap[child + 1].like == heap[child].like &&
heap[child + 1].date > heap[child].date)) {
child += 1;
}
}
if (like > heap[child].like ||
(like == heap[child].like && date < heap[child].date)) {
heap[hole].like = heap[child].like;
heap[hole].id = heap[child].id;
heap[hole].date = heap[child].date;
pos[heap[hole].id] = hole;
hole = child;
} else {
break;
}
}
heap[hole].id = id;
heap[hole].date = date;
heap[hole].like = like;
pos[id] = hole;
}


## yyong119's solution

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 2000010
using namespace std;
int n, m, cur_time;
int cd_seq[MAX_N], id_map[MAX_N], pos_map[MAX_N], time_seq[MAX_N];
char ch = getchar(); int res = 0, flag = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res * flag;
}
inline void swap_element(int x, int y) {
swap(cd_seq[x], cd_seq[y]);
swap(id_map[x], id_map[y]);
pos_map[id_map[x]] = x;
pos_map[id_map[y]] = y;
}
inline bool cmp(const int &x, const int &y) {
return (cd_seq[x] == cd_seq[y] ? time_seq[id_map[x]] > time_seq[id_map[y]] : cd_seq[x] < cd_seq[y]);
}
void push_down(int x) {
for (register int k = x; (k << 1) <= n;) {
int min_id = k, l = k << 1, r = k << 1 | 1;
// left child
if (cmp(l, min_id)) min_id = l;
// right child
if (r <= n && cmp(r, min_id)) min_id = r;
// check to push down
if (min_id == k) return;
swap_element(k, min_id);
k = min_id;
}
}
void push_up(int x) {
for (register int k = x; k > 1;) {
// parent
int p = k >> 1;
// chekc to push up
if (cmp(k, p)) {
swap_element(k, p);
k = p;
}
else return;
}
}
int main() {
for (register int i = 1; i <= n; ++i) {
id_map[i] = pos_map[i] = i;
time_seq[i] = ++cur_time;
}
for (register int i = (n >> 1); i > 0; --i)
push_down(i);
for (register int i = 0; i < m; ++i) {
time_seq[x] = ++cur_time;
if (diff == 1) {
++cd_seq[pos_map[x]];
push_down(pos_map[x]);
}
else {
--cd_seq[pos_map[x]];
push_up(pos_map[x]);
}
printf("%d\n", id_map[1]);
}
return 0;
}