二分+线段树 Codeforces609F Frogs and mosquitoes

78 阅读 0 评论 52 点赞

我是靠谱客的博主不安美女，最近开发中收集的这篇文章主要介绍二分+线段树 Codeforces609F Frogs and mosquitoes，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门：点击打开链接

题意：

有n青蛙和m蚊子(n,m<=1e5)，青蛙两个参数，位置xi，舌头长度ti
蚊子两个参数,位置pj,权值bj
只有当xi+ti>=pj时，第i只青蛙才能吃到第j只蚊子。
如果第j只蚊子能被多只青蛙吃到，那么xi最小的青蛙会把这只蚊子吃了
每次青蛙吃了某只蚊子以后，ti会增加蚊子的bj
输出n只青蛙吃的蚊子数，以及最后时候的舌头长度ti

蚊子会按照给出的时间顺序出现。

思路：我们先来考虑另一个问题

1.如何在[1,n]区间内找到最靠近左边的位置使得权值>=x

2.如何在[l,r]区间内找到最靠近左边的位置使得权值>=x

对于第一种，应该是比较熟悉的了，直接构建线段树维护最大值，然后查询的时候先考虑左子树，如果左子树的最大值>=x就往左边走，否则就往右边走。复杂度O(logn)

对于第二种，好像就没那么好维护了，然而我们仔细分析一下发现其实有单调性，可以考虑用二分来做

我们可以用线段树维护区间内权值最大值，然后用二分去枚举区间的右节点，查询[l,m]的最大值是否>=x,然后将它组逐渐向左边靠近即可，复杂度O(logn*logn)

这题，如果我们会上面的第二个问题，就很好解决了。

用线段树维护第i个位置的青蛙的xi+ti等于多少，区间维护最大值。

对于一只蚊子，直接用之前说的第二个问题的方法，就能找到符合要求的最左边的那只青蛙了。

另外，将暂时不能被青蛙吃掉的蚊子加入到multiset里面，一定要是multiset不是set，因为蚊子的坐标可能是一样的

然后某只青蛙的舌头伸长后，再去multiset里面找找，看此时能不能吃到其他的蚊子。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;

const int MX = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int rear, n, m;
int ans[MX]; LL tong[MX];
LL A[MX], B[MX], MAX[MX << 2];
PII mos[MX];

struct Data {
    int id;
    LL ti, xi;
    bool operator<(const Data &P) const {
        return xi < P.xi;
    }
} flog[MX];
void push_up(int rt) {
    MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    if(l == r) {
        MAX[rt] = A[l];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int x, LL d, int l, int r, int rt) {
    if(l == r) {
        MAX[rt] += d;
        return;
    }
    int m = (l + r) >> 1;
    if(x <= m) update(x, d, lson);
    else update(x, d, rson);
    push_up(rt);
}
LL query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return MAX[rt];
    }
    LL ret = 0;
    int m = (l + r) >> 1;
    if(L <= m) ret = max(ret, query(L, R, lson));
    if(R > m) ret = max(ret, query(L, R, rson));
    return ret;
}
int solve(LL pj) {
    int l = 1, m, r = upper_bound(B + 1, B + 1 + rear, pj) - B - 1;
    if(r == 0 || query(1, r, 1, n, 1) < pj) return -1;
    while(l <= r) {
        m = (l + r) >> 1;
        if(query(1, m, 1, n, 1) >= pj) r = m - 1;
        else l = m + 1;
    }
    return r + 1;
}

int main() {
    //FIN;
    while(~scanf("%d%d", &n, &m)) {
        rear = 0;
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; i++) {
            scanf("%I64d%I64d", &flog[i].xi, &flog[i].ti);
            flog[i].id = i;
        }
        sort(flog + 1, flog + n + 1);
        for(int i = 1; i <= n; i++) {
            A[i] = flog[i].xi + flog[i].ti;
            B[++rear] = flog[i].xi;
        }
        build(1, n, 1);

        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &mos[i].first, &mos[i].second);
        }

        multiset<PII>w;
        for(int i = 1; i <= m; i++) {
            int pos = solve(mos[i].first);
            if(pos != -1) {
                ans[flog[pos].id]++;
                flog[pos].ti += mos[i].second;
                update(pos, mos[i].second, 1, n, 1);
                LL r = flog[pos].xi + flog[pos].ti;
                while(!w.empty()) {
                    multiset<PII>::iterator t = w.lower_bound(PII(flog[pos].xi, 0));
                    if(t == w.end() || r < t->first) break;

                    r += t->second;
                    ans[flog[pos].id]++;
                    flog[pos].ti += t->second;
                    update(pos, t->second, 1, n, 1);
                    w.erase(t);
                }
            } else w.insert(mos[i]);
        }

        for(int i = 1; i <= n; i++) {
            tong[flog[i].id] = flog[i].ti;
        }
        for(int i = 1; i <= n; i++) {
            printf("%d %I64dn", ans[i], tong[i]);
        }
    }
    return 0;
}