2016年3月4日 星期五

[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]);
}

沒有留言:

張貼留言