[Codeforces 609F]Frogs and mosquitoes

這裡提供了另一種解法，選一個喜歡的去實現吧~

我們會需要求出對於某個$x$，最左邊的青蛙是哪隻

可以發現，這裡有一個性質
現在給定兩個點$p_{1}$和$p_{2}$ ($p_{1}<p_{2}$)
如果位於$p_{1}$的蚊子會被位於$x_{1}$的青蛙吃掉，位於$p_{2}$的蚊子會被位於$x_{2}$的青蛙吃掉
則可以推得$x_{1}<x_{2}$
反過來由$x_{1}<x_{2}$也可以推得$p_{1}<p_{2}$

這讓我們得以用$STL$的$map$實現使用$lower\_bound$查詢可以將舌頭伸到$p$右邊的青蛙中，最左邊的那隻青蛙 (每隻青蛙依照輸入順序被賦予一個$id$)，注意，這不代表這隻青蛙會在$p$的左邊
我把這個$map$命名為$happy$ (有可能吃到蚊子的青蛙很開心(?) )

我們可以先把青蛙依照$x$排序，然後一個個嘗試加入$happy$裡面
當某隻青蛙的舌頭可以伸到破紀錄遠的地方，就把這隻青蛙加進去，$key$是這隻青蛙舌頭可以伸到最遠的位置 (稱為$reach$)，$value$是這隻青蛙的$id$
否則，代表這隻可憐的青蛙永遠吃不到蚊子
$happy$建好了(?)
記得將青蛙依照$id$ (輸入順序) 排回來，以後取得$id$後才能找到並修改這隻青蛙

當某隻蚊子降落在$p$點，我們可以用$lower\_bound$得到可以將舌頭伸到$p$右邊的青蛙中，最左邊的那隻
如果這隻青蛙不存在或者它位於$p$的右邊，代表這隻蚊子幸運活了下來，加入$alive$裡面
否則
這隻青蛙的舌頭會變長，意味著它的$reach$也會隨之改變，為了維持$happy$的正確性，在修改這隻青蛙前，先將它從$happy$裡面移除
舌頭變長後，用$lower\_bound$檢查看看$alive$裡面有沒有可以吃掉的蚊子，一直吃直到沒有蚊子可以吃為止
把$happy$裡面所有$x$更大且$reach$更小的青蛙刪除 (它們的蚊子將全部被這隻青蛙搶走)，然後把這隻青蛙加回去

記錄下每隻青蛙吃了多少蚊子、舌頭多長，最後輸出答案

時間複雜度：$O(N\log N+M\log N)$

code:

#include<cstdio>
#include<cassert>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct Frog
{
    int x,reach,id,eat;
    Frog(){}
    Frog(const int _x,const int _reach,const int _id):x(_x),reach(_reach),id(_id),eat(0){}
    bool operator<(const Frog &f)const{return reach<f.reach;}
};
int N,M;
bool EatMosquito(const Frog &frog,multimap<int,int>&alive,int &b)
{
    auto it=alive.lower_bound(frog.x);
    if(it==alive.end()||(it->first)>frog.reach)return false;
    b=it->second;
    alive.erase(it);
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        vector<Frog>frogs;//all frogs
        for(int i=0,x,t;i<N;i++)scanf("%d%d",&x,&t),frogs.push_back(Frog(x,x+t,i));
        sort(frogs.begin(),frogs.end(),[](const Frog &a,const Frog &b)->bool{return a.x<b.x;});
        map<int,int>happy;//frogs possible to eat mosquitoes
        for(const Frog &f:frogs)if(happy.empty()||f.reach>(happy.rbegin()->first))happy[f.reach]=f.id;
        sort(frogs.begin(),frogs.end(),[](const Frog &a,const Frog &b)->bool{return a.id<b.id;});
        multimap<int,int>alive;//mosquitoes still alive
        for(int i=0,p,b;i<M;i++)
        {
            scanf("%d%d",&p,&b);
            auto it=happy.lower_bound(p);
            if(it!=happy.end()&&frogs[it->second].x<=p)
            {
                Frog &frog=frogs[it->second];
                happy.erase(it++);
                do
                {
                    frog.reach+=b;
                    frog.eat++;
                    while(it!=happy.end()&&(it->first)<=frog.reach)happy.erase(it++);
                }while(EatMosquito(frog,alive,b));
                happy[frog.reach]=frog.id;
            }
            else alive.insert(make_pair(p,b));
        }
        for(int i=0;i<N;i++)printf("%d %d\n",frogs[i].eat,frogs[i].reach-frogs[i].x);
    }
    return 0;
}