[Educational Round 3][Codeforces 609F. Frogs and mosquitoes]

这题拖了快一周_(:з」∠)_就把这货单独拿出来溜溜吧~

题目大意：在(x)轴上有(n)只青蛙，每只青蛙有对应的位置(x_i)和他舌头的长度(t_i)，青蛙可以吃到位置在([x_i,t_i])内的蚊子。(m)只蚊子依次降落在位置(p_i)上，如果这只蚊子在某只青蛙的攻击范围内，那么他会被这只青蛙吃掉，若有多只青蛙可以吃掉这只蚊子，处在最左边位置的青蛙会吃掉他，吃掉这只蚊子的青蛙舌头长度会增长(b_i)。若舌头增长后可以吃掉尚还存活的蚊子，则这只青蛙会继续吃他能吃到的所有蚊子。问最后每只青蛙能吃到的蚊子数目(c_i)和最终的舌头长度(l_i)。

题解：考虑用树状数组维护坐标小于(x)的青蛙最远能吃到哪，由于(x_i)的范围较大所以需要离散化处理，之后就是树状数组求区间最大值的问题。开一个(pair<int,int>a[N])，记录位置第(i)小的青蛙对应的位置及其标号，那么每次进来一只蚊子可以用lowerbound/upperbound来确定最后一只在(p_i)左边的青蛙，之后再进行二分查找，找出能吃到这只蚊子的青蛙并模拟吃蚊子的过程即可。注意一下对暂时不会被吃掉的蚊子的特判。

#include<bits/stdc++.h>
using namespace std;
#define N 200001
#define LL long long
#define mp make_pair
pair<LL,LL>a[N];
set<pair<LL,LL> >mos;
LL n,m,x[N],t[N],p,b[N],f[N],c[N];
LL lowbit(LL x){return x&(-x);}
void change(LL x,LL c){while(x<N)f[x]=max(f[x],c),x+=lowbit(x);}
LL ask(LL x){LL res=0;while(x>0)res=max(res,f[x]),x-=lowbit(x);return res;}
int main()
{
    scanf("%I64d%I64d",&n,&m);
    for(LL i=1;i<=n;i++)
      scanf("%I64d%I64d",&x[i],&t[i]),a[i]=mp(x[i],i);
    sort(a+1,a+n+1);
    for(LL i=1;i<=n;i++)change(i,x[a[i].second]+t[a[i].second]);
    for(LL i=1;i<=m;i++)
      {
      scanf("%I64d%I64d",&p,&b[i]);
      LL l=1,r=upper_bound(a+1,a+n+1,mp(p,n))-a-1;
      if(p<a[1].first)continue;
      if(p>ask(r)){mos.insert(mp(p,i));continue;}
      while(l<r)
        {
        LL mid=l+r>>1;
        if(ask(mid)>=p)r=mid;
        else l=mid+1;
        }
      if(a[l].first>p){mos.insert(mp(p,i));continue;}
      LL id=a[l].second;
      t[id]+=b[i],change(l,x[id]+t[id]),c[id]++;
      for(auto it=mos.lower_bound(mp(x[id],0));it!=mos.end() && (*it).first<=x[id]+t[id];)
        t[id]+=b[(*it).second],change(l,x[id]+t[id]),c[id]++,mos.erase(it++);
      }
    for(LL i=1;i<=n;i++)
      printf("%I64d %I64d
",c[i],t[i]);
    return 0;
}

View Code