[Educational Codeforces Round 3 pF][Segment Tree]Frogs and mosquitoes

原題連結
不知道為什麼一道很單純的題目不但被我弄得很複雜，而且搞了很久(?

思路應該不難：我們對座標開一個線段樹，樹上紀錄這一段區間是哪隻青蛙會吃到的。當然，使用copy on write技巧，不然根本開不下XD

特別的地方是，與一般的線段樹不同，不需要做任何的push or pull操作，只需要在更新時對val取min。
這是因為我們查詢的特性：總是單點查詢，而且每個座標點在同個時間最多對應到唯一的青蛙。

說說主過程。首先建好一開始的線段樹，當有蚊子飛進來時就單點查詢一下有沒有人能吃他，如果沒有就先把他放進set裡面養起來(?
如果有的話就更新一下能吃到蚊子的青蛙的舌頭長度，然後看看能否吃到更多(?的蚊子，這可以藉由set內建lower_bound去做。
確認吃夠了之後記得更新一次線段樹確保結果正確。

最後說說我遇到的bug。我總共寫出了2個bug，2個都簡直了。
第一個是我最開始想到的作法，用區間賦值配合硬是弄出來的有序性去做，結果tag忘了設成-1，這就傳了6個WA。
第二個是我忘了開multiset，再傳了快10個WA。

......唉

另外還有一個我個人相當喜歡的解法，可以參考這裡

#include<cstdio>
#include<set>
using namespace std;
const int maxn=200000+5;
const int maxc=1000000000;
const int maxm=200000+5;
const int INF=(1<<30);
struct Node
{
    Node *lc,*rc;
    int val;
    Node() {val=INF;lc=rc=NULL;}
}*root;
int ml,mr,mv;
int eat[maxn],pos[maxn],ton[maxn];
void modify(Node*& now,int L,int R)
{
    if(!now) now=new Node();
    int M=L+(R-L)/2;
    if(ml<= L && R<=mr)
    {
        if(now->val==INF || pos[mv]<pos[now->val]) now->val=mv;
        return;
    }
    if(ml<=M) modify(now->lc,L,M);
    if(mr >M) modify(now->rc,M+1,R);
}
int qx,qv;
void query(Node*& now,int L,int R)
{
    if(!now) now=new Node();
    if(qv==INF || (now->val!=INF && pos[now->val]<pos[qv])) qv=now->val;
    if(L==R) return;
    int M=L+(R-L)/2;
    if(qx<=M) query(now->lc,L,M);
    else query(now->rc,M+1,R);
}
multiset<pair<int,int> > mos;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",pos+i,ton+i);
    for(int i=1;i<=n;i++)
    {
        ml=pos[i],mr=pos[i]+ton[i],mv=i;
        modify(root,0,maxc);
    }
    for(int i=0,a,b;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        
        mos.insert(make_pair(a,b));

        qx=a,qv=INF;
        query(root,0,maxc);
        if(qv==INF) continue;
        ton[qv]+=b;
        eat[qv]++;
        mos.erase(make_pair(a,b));
        for(auto it=mos.lower_bound(make_pair(pos[qv],-1));it!=mos.end();it=mos.lower_bound(make_pair(pos[qv],-1))) 
        {
            if(it==mos.end() || it->first>pos[qv]+ton[qv]) break;
            ton[qv]+=it->second;
            eat[qv]++;
            mos.erase(it); 
        }
        ml=pos[qv];
        mr=min(pos[qv]+ton[qv],maxc);
        mv=qv;
        modify(root,0,maxc);
    }
    for(int i=1;i<=n;i++) printf("%d %d\n",eat[i],ton[i]);
}