11990: 【原1990】二哥听CD

题目描述

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

题目描述

二哥有很多CD，每次想听它们的时候都不知道挑哪个好。

为了方便自己选CD，现在二哥给他所有的CD一个整数作为好感度。显然，好感度肯定不是永远不变的，随着时间的变化，某些CD的好感度也会发生变化。

现在给你一个长度为N的整数序列，序列的第i个表示编号为i的CD的初始好感度，这里保证第i张CD的初始好感度大于等于第i-1张的初始好感度。接下来会给你M对整数x和y，表示在第i天编号x的CD好感度会增加y（y为1或-1），你需要求出在每次变化后二哥好感度最低的CD是哪张，如果有多张好感度都是最低的，那么选最后变成这个好感度的CD，在这里我们假设在初始序列中编号i的CD的变化到初始好感度的时间晚于编号i-1的CD变化到其初始好感度的时间。

输入格式

输入共有两行。

第1行两个整数N和M，表示CD数和需要询问的天数。

第2行有n个整数，表示初始好感度。

接下来M行，每行两个整数x,y，表示M次询问。

输出格式

对于每次询问输出这次变化后所求的CD编号。一个询问占一行。

说明

对于30%的数据：\(1 \leq n, m \leq 100\)。对于60%数据：\(1 \leq n, m \leq 100,000\)。对于全部数据：任何时刻好感度不会超过有符号32位整数，\(1 \leq n, m \leq 2,000,000\)。

注意：时限比较紧，请仔细估计复杂度，并建议不要使用STL，否则容易超时。

样例输入

样例输出

限制

时间限制：2000ms，内存限制：262144kb。

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];
inline int read() {
    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() {
    n = read(), m = read();
    for (register int i = 1; i <= n; ++i) {
        cd_seq[i] = read();
        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) {
        int x = read(), diff = read();
        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;
}