[Codeforces 609F]Frogs and mosquitoes

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

我們可以先把青蛙依照位置排序，然後依序給它們編號，這樣一來編號越小代表$x$座標越小

接著，可以對$x$座標建一棵$copy-on-write$的線段樹，然後就可以對每個$x$座標維護舌頭可以伸到的青蛙中最小的編號了

當有一個位置沒有青蛙的舌頭可以到達，編號設為$INF$

由於是維護最小值，而且可以確定在區間修改的時候可以把區間中的最小值留住
因此不需要特別維護 ($Maintain$) 或者下放標記 ($PutDown$)
只要在$query$的時候取路徑中$O(\log(x範圍))$個節點的最小值就好了

當某隻蚊子目前無法被任何青蛙吃掉時，可以先存進$set$裡面
每當有青蛙吃掉蚊子讓舌頭變長時，就用$lower\_bound$檢查看看有沒有之前吃不掉的蚊子現在可以吃掉了
一直吃直到沒有吃得到的蚊子為止

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

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
using namespace std;
const int INF=2147483647,MAX_COORDINATE=1000000000;
void getmin(int &a,const int b){if(b<a)a=b;}
struct Node
{
    Node *ch[2];
    int mn;
    Node(const int _mn):ch{NULL,NULL},mn(_mn){}
}*ROOT;
void PutDown(Node *o)
{
    for(int d=0;d<2;d++)
    {
        if(!o->ch[d])o->ch[d]=new Node(o->mn);
        getmin(o->ch[d]->mn,o->mn);//no need actually
    }
}
void Modify(Node *o,const int l,const int r,const int bl,const int br,const int val)
{
    assert(o);
    if(r<bl||br<l||o->mn<=val)return;
    if(bl<=l&&r<=br){o->mn=val;return;}
    const int mid=(l+r)/2;
    PutDown(o);
    Modify(o->ch[0],l,mid,bl,br,val),Modify(o->ch[1],mid+1,r,bl,br,val);
}
void Query(Node *o,const int l,const int r,const int loc,int &ans)
{
    if(!o)return;
    getmin(ans,o->mn);
    assert(l<=loc&&loc<=r);
    const int mid=(l+r)/2;
    if(loc<=mid)Query(o->ch[0],l,mid,loc,ans);
    else Query(o->ch[1],mid+1,r,loc,ans);
}
struct Frog
{
    int id,x,tongue,eaten;
    Frog(){}
    Frog(const int _id,const int _x,const int _tongue):id(_id),x(_x),tongue(_tongue),eaten(0){}
};
void Modify(const Frog &f,int val){Modify(ROOT,0,MAX_COORDINATE,f.x,f.x+f.tongue,val);}
int Query(const int loc){int ans=INF;Query(ROOT,0,MAX_COORDINATE,loc,ans);return ans;}
int N,M;
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        vector<Frog>frogs;
        for(int i=0,x,t;i<N;i++)scanf("%d%d",&x,&t),frogs.push_back(Frog(i,x,t));
        sort(frogs.begin(),frogs.end(),[](const Frog &a,const Frog &b)->bool{return a.x<b.x;});
        ROOT=new Node(INF);
        for(int i=0;i<N;i++)Modify(frogs[i],i);
//        for(int i=0;i<=MAX_COORDINATE;i++)printf("%d ",Query(i));puts("");
        multiset<pair<int,int> >alive;
        for(int i=0,p,b;i<M;i++)
        {
            scanf("%d%d",&p,&b);
            int result=Query(p);
            if(result==INF)alive.insert(make_pair(p,b));
            else
            {
                Frog &f=frogs[result];
                f.tongue+=b;
                f.eaten++;
                for(auto it=alive.lower_bound(make_pair(f.x,-INF));it!=alive.end();it=alive.lower_bound(make_pair(f.x,-INF)))
                {
                    if((it->first)>f.x+f.tongue)break;
                    f.tongue+=it->second;
                    f.eaten++;
                    alive.erase(it);
                }
                Modify(f,result);
            }
        }
        sort(frogs.begin(),frogs.end(),[](const Frog &a,const Frog &b)->bool{return a.id<b.id;});
        for(int i=0;i<N;i++)printf("%d %d\n",frogs[i].eaten,frogs[i].tongue);
    }
    return 0;
}