题解：P5819 【L&K R-03】音游大计算

HenghengMoi · 2024-10-18 23:39:55 · 题解

P5819 【L&K R-03】音游大计算

题意简述

非常长题目，使人简述不了，爱来自大模拟。

题目分析

浮点数小数位数不超过 5 位，大小不超过 10^4，乘 10^5 便于后续处理。

首先肯定要将 key 和小 K 的点击按时间排序。对于小 K 的每次点击，寻找满足 a_i \le x \le b_i 的 t_i 最小的若干个 key，判定后删除。key 的实际判定时间与 t_i 可能不同，一边判定一边计算分数会特别麻烦，可以到最后再将 key 按实际判定时间排序后计算。

但是暴力会超时，因为寻找 key 的时间复杂度最坏为 O(nm)。

考虑优化。

由于只查询 m 个位置上的 key，对 x 离散化，只维护这 m 个位置的信息即可。

对于每个 key，在 [a_i, b_i] 上修改；对于每次点击，查询 x_i 的信息。

区间修改，单点查询。

使用线段树优化。树上每个节点维护一个链表，每次从链表一端插入 t_i 大的 key，从另一端删除已判定的 t_i 小的 key。

可是在极限数据下，一开始根节点有一条长度为 n 的链（即 n 个 key 都可能被小 K 的任意一次点击判定到），再在 m 个点都分别进行一次询问，那么一条长度为 n 的链就会被下传成 m 条长度为 n 的链，空间复杂度会达到 O(nm)。

那干脆就不下传了，只保证单条链内的 t_i 单调。

对于每次插入操作，一旦确定了修改的节点位置，后续就不再上传或下传，一次操作的空间复杂度为 O(\log{m})，总空间复杂度 O(n\log{m})。

对于每次查询操作，查询从该叶子节点到根节点的路径上链表维护的 t_{min}，一次操作的时间复杂度为 O(\log{m})，由于 t_{min} 可能相同，最多可能需要 n + m 次查询，总时间复杂度 O((n + m)\log{m})。

还可以使用动态开点线段树，这样就最多有 2m - 1 个节点。

大体思路确定了，接下来开始扣细节。

代码

首先把 key 和点击的信息塞进结构体里。

const int N = 114514;

struct NOTE {
    int t, l, r;
    int judge, judge_t; //判定等级 & 判定时间 
    bool operator < (const NOTE &nt) const {
        return t < nt.t || t == nt.t && l < nt.l || t == nt.t && l == nt.l && r < nt.r;
    }
}note[N + 5];

struct TAP {
    int t, x;
    bool operator < (const TAP &tp) const {
        return t < tp.t;
    }
}tap[N + 5];

输入时 double 有误差，可以加上 0.00005 之后再乘 10^5。

double db; 
int n, m;
int a[N + 5], len; //离散化

int main() {
    /**/
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> db;
        db += 0.000005;
        note[i].t = db * 100000;
        cin >> db;
        db += 0.000005;
        note[i].l = db * 100000;
        cin >> db;
        db += 0.000005;
        note[i].r = db * 100000;
    }
    for (int i = 1; i <= m; i++) {
        cin >> db;
        db += 0.000005;
        tap[i].t = db * 100000;
        cin >> db;
        db += 0.000005;
        tap[i].x = db * 100000;
        a[++len] = tap[i].x;
    }

    //离散化
    sort(a + 1, a + len + 1);
    len = unique(a + 1, a + len + 1) - a - 1;
    for (int i = 1; i <= m; i++) tap[i].x = lower_bound(a + 1, a + len + 1, tap[i].x) - a;
    /**/
}

分享一个小知识：手写 list 比用 std::list 快。写一个结构体封装 list，需要实现头插入，尾查询，尾删除，查询是否为空。（虽然用 STL 也慢不了多少）

struct LIST {

    struct node{
        int val; //权值 
        node* l; //左节点 
        node* r; //右节点 
    }front[2 * N + 5], back[2 * N + 5]; //链表头尾 

    void init() { //初始化 
        for (int i = 1; i <= 2 * N; i++) {
            front[i].l = NULL;
            back[i].r = NULL;
            front[i].r = &back[i];
            back[i].l = &front[i];
        }
    }

    void push_front(int t, int k) {
        node *p = new node;
        p -> val = k;
        front[t].r -> l = p;
        p -> r = front[t].r;
        front[t].r = p;
        p -> l = &front[t];
    }

    void pop_back(int t) {
        node *p = back[t].l;
        p -> l -> r = &back[t];
        back[t].l = p -> l;
        p -> l = NULL;
        p -> r = NULL;
        delete p;
    }

    int get_back(int t) {
        return back[t].l -> val;
    }

    bool empty(int t) {
        return front[t].r == &back[t];
    }

}List;

线段树上甚至不用维护多少信息，直接在链表上操作即可。由于先插入的 key 在删除时不一定在链表尾部，只能打上删除标记，查询时更新。

bool vis[N + 5]; //删除标记

struct Segment{

    int tot, ls[2 * N + 5], rs[2 * N + 5];

    void pushdown(int t) { //很不pushdown的pushdown，删除链表尾部被标记了的key 
        while (!List.empty(t) && vis[List.get_back(t)]) List.pop_back(t);
    }

    void build(int l = 1, int r = len, int t = 1) { //动态开点建树 
        if (l == r) return;
        int mid = (l + r) >> 1;
        ls[t] = ++tot;
        build(l, mid, ls[t]);
        rs[t] = ++tot;
        build(mid + 1, r, rs[t]);
    }

    void insert(int L, int R, int k, int l = 1, int r = len, int t = 1) {
        if (!t) return;
        if (L <= l && r <= R) {
            List.push_front(t, k);
            return; 
        }
        int mid = (l + r) >> 1;
        if (R <= mid) insert(L, R, k, l, mid, ls[t]);
        else if (L > mid) insert(L, R, k, mid + 1, r, rs[t]);
        else {
            insert(L, R, k, l, mid, ls[t]);
            insert(L, R, k, mid + 1, r, rs[t]);
        }
    }

    int query(int p, int l = 1, int r = len, int t = 1) {
        if (!t) return 0;
        pushdown(t);
        int ret = 0;
        if (!List.empty(t)) ret = List.get_back(t);
        if (l == r) return ret;
        int mid = (l + r) >> 1;
        if (p <= mid) {
            int L = query(p, l, mid, ls[t]);
            if (L == 0) return ret;
            else if (ret == 0) return L;
            else if (note[L].t < note[ret].t) return L;
            else return ret;
        }
        else {
            int R = query(p, mid + 1, r, rs[t]);
            if (R == 0) return ret;
            else if (ret == 0) return R;
            else if (note[R].t < note[ret].t) return R;
            else return ret;
        }
    }

}tree;

每次点击要判定完重合的 key，记得给已判定的 key 打上删除标记，判定区间的符号不要写错，特判到最后都没有判定到的 key。

int L, R; //双指针 
bool vis[N + 5]; //删除标记 
vector<int> ret_notes; //一次判定到的key

int main() {
    /**/
    for (int i = 1; i <= m; i++) {
        while (L <= n && note[L].t < tap[i].t + 100000) { //更新上界
            int l = lower_bound(a + 1, a + len + 1, note[L].l) - a;
            int r = upper_bound(a + 1, a + len + 1, note[L].r) - a - 1;
            tree.insert(l, r, L);
            L++;
        }
        while (R <= L && note[R].t <= tap[i].t - 60000) { //更新下界
            if (!vis[R]) { //落出屏幕前仍未判定
                note[R].judge = 0;
                note[R].judge_t = note[R].t + 60000;
                vis[R] = 1;
            }
            R++;
        }
        int ret = tree.query(tap[i].x);
        if (ret == 0) continue;
        ret_notes.clear();
        int T = note[ret].t;
        while (ret != 0 && note[ret].t == T) { //判定重合的key
            ret_notes.push_back(ret);
            vis[ret] = 1;
            ret = tree.query(tap[i].x);
        }
        T -= tap[i].t;
        int judgement = 0;
        if (T >= 60000) judgement = 0;
        else if (T >= 20000) judgement = 1;
        else if (T > -20000) judgement = 2;
        else judgement = 1;
        for (int j = 0; j < ret_notes.size(); j++) {
            ret = ret_notes[j];
            note[ret].judge = judgement;
            note[ret].judge_t = tap[i].t;
        }
    }
    for (int i = R; i <= n; i++) {
        if (!vis[i]) { //所有点击操作结束后仍未判定
            note[i].judge = 0;
            note[i].judge_t = note[i].t + 60000;
        }
    }
    /**/
}

统计答案前以实际判定时间为第一关键字，判定等级为第二关键字排序。

int cnt_judge[3], combo, max_combo; //计算答案

bool cmp(NOTE i, NOTE j) {
    return i.judge_t < j.judge_t || i.judge_t == j.judge_t && i.judge < j.judge;
}

int main() {
    /**/
    //计算答案
    sort(note + 1, note + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        cnt_judge[note[i].judge]++;
        if (note[i].judge == 0) combo = 0;
        else combo++;
        max_combo = max(max_combo, combo);
    }
    cout << cnt_judge[2] << ' ' << cnt_judge[1] << ' ' << cnt_judge[0] << ' ' << max_combo;
    /**/
}

完整代码

后记

看到数据这么水天都塌了。

一开始链表判空写成 return front[t].l == &back[t];，还是 AC。

欢迎大家用各种神奇妙妙做法 AC。