跳转至

CF609F

知识点

  • 线段树
  • set

题意简述

给定数轴非负半轴上的 \(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\)

  • 如果 \(\textrm{dat}(2p) \ge p_i\),即左儿子节点有青蛙可以吃掉这只蚊子,那肯定是优先选更靠左的青蛙吃掉,向左儿子递归;
  • 否则如果 \(\textrm{dat}(2p + 1) \ge p_i\),即右儿子节点有青蛙可以吃掉这只蚊子,那就往右儿子递归。
  • 如果到了一个叶子节点,说明这个节点表示的青蛙要吃掉当前蚊子了,更新 \(l_i\)\(\textrm{eat}(p)\)(表示这只青蛙吃了多少只蚊子)以及 \(\textrm{dat}(p)\)

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

代码实现

核心部分已用高亮标出。

Code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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;
}

  1. 原题链接: F. Frogs and mosquitoes