[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=;while(x>)res=max(res,f[x]),x-=lowbit(x);return res;}

int main()

{

    scanf("%I64d%I64d",&n,&m);

    for(LL i=;i<=n;i++)

      scanf("%I64d%I64d",&x[i],&t[i]),a[i]=mp(x[i],i);

    sort(a+,a+n+);

    for(LL i=;i<=n;i++)change(i,x[a[i].second]+t[a[i].second]);

    for(LL i=;i<=m;i++)

      {

      scanf("%I64d%I64d",&p,&b[i]);

      LL l=,r=upper_bound(a+,a+n+,mp(p,n))-a-;

      if(p<a[].first)continue;

      if(p>ask(r)){mos.insert(mp(p,i));continue;}

      while(l<r)

        {

        LL mid=l+r>>;

        if(ask(mid)>=p)r=mid;

        else l=mid+;

        }

      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],));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=;i<=n;i++)

      printf("%I64d %I64d\n",c[i],t[i]);

    return ;

}

秒客网

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

相关文章