[]
namespace MappingBinaryHeap{
/*
DS:
Datastructure to show the value
Heap:
1.Ds:value
2.idx:index
pos:
The position for each index
len:
The volum n of heap
hh:
heap
Push:
insert an element
Pop:
pop an element:
1.pop(pos[]) pop the element index
2.pop(1) pop the 'max' one
*/
struct DS{
int next;
DS(){}
DS(int x) : next(x){}
bool operator <(const DS &A) const {
if (next == -1)
return true;
if (A.next == -1)
return false;
return next > A.next;
}
void init() {
next = 0;
}
};
#define maxn 100005
struct Heap {
int idx;
DS val;
}hh[maxn];
int pos[maxn];
int len;
bool Prior(Heap a, Heap b) {
return a.val < b.val;
}
void Push(Heap s) {
int i;
for (i = ++len; i > 1 && Prior(s, hh[i / 2]); i /= 2) {
hh[i] = hh[i / 2];
pos[hh[i].idx] = i;
}
hh[i] = s;
pos[hh[i].idx] = i;
}
Heap Pop(int idx) {
if (idx == -1)
return hh[0];
Heap ret = hh[idx];
Heap last = hh[len--];
int i, s;
for (i = idx; i * 2 <= len; i = s) {
s = i * 2;
if (s + 1 <= len && Prior(hh[s + 1], hh[s])) {
s++;
}
if (Prior(hh[s], last)) {
hh[i] = hh[s];
pos[hh[i].idx] = i;
} else {
break;
}
}
hh[i] = last;
pos[hh[i].idx] = i;
for (i = idx; i > 1 && Prior(hh[i], hh[i / 2]); i /= 2) {
Heap buf = hh[i];
hh[i] = hh[i / 2];
hh[i / 2] = buf;
pos[hh[i].idx] = i;
pos[hh[i / 2].idx] = i / 2;
}
return ret;
}
void init() {
hh[0].val.init();
len = 0;
}
};

namespace MappingBinaryHeap{
/*
DS:
Datastructure to show the value
Heap:
1.Ds:value
2.idx:index
pos:
The position for each index
len:
The volum n of heap
hh:
heap
Push:
insert an element
Pop:
pop an element:
1.pop(pos[]) pop the element index
2.pop(1) pop the 'max' one
*/
struct DS{
int next;
DS(){}
DS(int x) : next(x){}
bool operator <(const DS &A) const {
if (next == -1)
return true;
if (A.next == -1)
return false;
return next > A.next;
}
void init() {
next = 0;
}
};
#define maxn 100005
struct Heap {
int idx;
DS val;
}hh[maxn];
int pos[maxn];
int len;
bool Prior(Heap a, Heap b) {
return a.val < b.val;
}
void Push(Heap s) {
int i;
for (i = ++len; i > 1 && Prior(s, hh[i / 2]); i /= 2) {
hh[i] = hh[i / 2];
pos[hh[i].idx] = i;
}
hh[i] = s;
pos[hh[i].idx] = i;
}
Heap Pop(int idx) {
if (idx == -1)
return hh[0];
Heap ret = hh[idx];
Heap last = hh[len--];
int i, s;
for (i = idx; i * 2 <= len; i = s) {
s = i * 2;
if (s + 1 <= len && Prior(hh[s + 1], hh[s])) {
s++;
}
if (Prior(hh[s], last)) {
hh[i] = hh[s];
pos[hh[i].idx] = i;
} else {
break;
}
}
hh[i] = last;
pos[hh[i].idx] = i;
for (i = idx; i > 1 && Prior(hh[i], hh[i / 2]); i /= 2) {
Heap buf = hh[i];
hh[i] = hh[i / 2];
hh[i / 2] = buf;
pos[hh[i].idx] = i;
pos[hh[i / 2].idx] = i / 2;
}
return ret;
}
void init() {
hh[0].val.init();
len = 0;
}
};