题解 CF609F 【Frogs and mosquitoes】

· · 题解

题意简述

给定数轴非负半轴上的 n 只青蛙的位置 x_i 以及舌头长度 l_i，还有依次落下来的 m 只蚊子的位置 p_i 以及大小 b_i。

每只蚊子 j 仅会被满足 x_i \le p_j \land x_i + l_i \ge p_j，且 i 最小的青蛙吃掉，吃之后 l_i \gets l_i + b_j。

问最后每只青蛙吃掉的蚊子的数量以及最后每只青蛙舌头的长度[^1]。

数据范围：1 \le n, m \le 2\cdot 10^5，1 \le x_i, l_i, p_i, b_i \le 10^9。

解题思路

我们实际上要解决的问题，是每只蚊子落下来了之后，被哪只青蛙吃掉。

首先离散化，然后维护区间中 x_i + l_i 的最大值 \textrm{dat}(p)。

注意到一只蚊子可能落下来的时候没有青蛙能吃到，但是之后某只青蛙的舌头变长了，能吃到它了；因此我们需要一个 multiset 来维护没吃掉的蚊子。

当在线段树上位于一个 \textrm{dat}(p) < p_i 的节点时，肯定这只蚊子是吃不掉的了，把它丢进一个 multiset 里存着以后吃。

如果当前节点满足 \textrm{dat}(p) \ge p_i：

在更新 l_i 的时候，看当前的青蛙在 multiset 里能不能吃更多的蚊子；实现上就是在 multiset 里 lower_bound，找 p_j 大于等于 x_i 的第一只蚊子 j 能否被 i 吃掉，顺着吃。

代码实现

#include <bits/stdc++.h>
#define LL long long

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
            if(f) _x = -_x;
        }
        template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
            read(_f), read(args ...);
        }
        inline void _deal(char ch) { putchar(ch); }
        template <typename T> inline void _deal(T _x) {
            if (_x < 0) putchar('-'), _x = -_x;
            if (_x > 9) _deal(_x / 10);
            putchar(_x % 10 + '0');
        }
        inline void write() {}
        template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
            _deal(_f), write(args...);
        }
    }

const int N = 2e5 + 5;
const int M = 2e5 + 5;

int n, m, x[N], t[N], rk[N];

std::multiset<std::pair<int, int> > ms;
std::pair<int, LL> ans[M];

bool cmp(int aa, int bb) {
    return x[aa] < x[bb];
}

struct SEGTREE {
    static const int MS = N * 4;
    LL dat[MS];
    int eat[MS], frm[MS];
    void pushup(int p) {
        dat[p] = std::max(dat[p << 1], dat[p << 1 | 1]);
    }
    void build(int p, int L, int R) {
        if(L == R) {
            dat[p] = x[rk[L]] + t[rk[L]];
            eat[p] = 0;
            frm[p] = x[rk[L]];
            return;
        }
        int MID = L + R >> 1;
        build(p << 1, L, MID), build(p << 1 | 1, MID + 1, R);
        pushup(p);
    }
    void solve(int p, int L, int R, int pos, int siz) {
        if(dat[p] < pos) {
            ms.insert(std::make_pair(pos, siz));
            return;
        }
        if(L == R) {
            if(frm[p] > pos)
                ms.insert(std::make_pair(pos, siz));
            else {
                dat[p] += siz, ++eat[p];
                for(std::multiset<std::pair<int, int> >::iterator it = ms.lower_bound(std::make_pair(frm[p], -1)); it != ms.end();) {
                    if(it->first > dat[p])
                        break;
                    else {
                        dat[p] += it->second;
                        ++eat[p];
                        std::multiset<std::pair<int, int> >::iterator tmp = it;
                        ++it;
                        ms.erase(tmp);
                    }
                }
            }
            return;
        }
        int MID = L + R >> 1;
        if(dat[p << 1] >= pos)
            solve(p << 1, L, MID, pos, siz);
        else if(dat[p << 1 | 1] >= pos)
            solve(p << 1 | 1, MID + 1, R, pos, siz);
        pushup(p);
    }
    std::pair<int, LL> query(int p, int L, int R, int x) {
        if(L == R)
            return std::make_pair(eat[p], dat[p] - frm[p]);
        int MID = L + R >> 1;
        if(x <= MID)
            return query(p << 1, L, MID, x);
        else
            return query(p << 1 | 1, MID + 1, R, x);
    }
} tr;

int32_t main() {
    io::read(n, m);
    for(int i = 1; i <= n; ++i) {
        io::read(x[i], t[i]);
        rk[i] = i;
    }
    std::sort(rk + 1, rk + n + 1, cmp);
    tr.build(1, 1, n);
    for(int i = 1; i <= m; ++i) {
        int ttp, ttb;
        io::read(ttp, ttb);
        tr.solve(1, 1, n, ttp, ttb);
    }
    for(int i = 1; i <= n; ++i)
        ans[rk[i]] = tr.query(1, 1, n, i);
    for(int i = 1; i <= n; ++i)
        printf("%d %lld\n", ans[i].first, ans[i].second);
    return 0;
}

原题链接: F. Frogs and mosquitoes