HDU5596/BestCoder Round #66 (div.2) 二分BIT/贪心

时间：2021-04-11 16:29:59

GTW likes gt

 
 Memory Limit: 131072/131072 K (Java/Others)
问题描述
从前，有nn只萌萌的GT，他们分成了两组在一起玩游戏。他们会排列成一排，第ii只GT会随机得到一个能力值b_ib​i​​。在第ii秒的时候，第ii只GT可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的GT。

为了使游戏更加有趣，GT的首领GTW会发功mm次，第ii次发功的时间为c_ic​i​​，则在第c_ic​i​​秒结束后，b_1,b_2,...,b_{c_i}b​1​​,b​2​​,...,b​c​i​​​​都会增加1。

现在，GTW想知道在第nn秒之后，会有几只GT存活下来。
输入描述
第一行只有一个整数T(T\leq 5)T(T≤5)，表示测试数据组数。

第二行有两个整数n,mn,m。表示GT的个数和GTW发功的次数。(1\leq n \leq 50000,1\leq m\leq 500001≤n≤50000,1≤m≤50000)

第三到n+2n+2行，每行有两个整数a_i,b_ia​i​​,b​i​​，表示第ii只GT在哪个组和他的能力值 (0\leq a[i]\leq 1,1\leq b[i]\leq 10^6)(0≤a[i]≤1,1≤b[i]≤10​6​​)

第n+3n+3行到第n+m+2n+m+2行，每行有一个整数c_ic​i​​,表示GTW第ii次发功的时间。1\leq c[i]\leq n1≤c[i]≤n
输出描述
总共TT行，第ii行表示第ii组数据中，GT存活的个数。
输入样例
1

4 3

0 3

1 2

0 3

1 1

1

3

4
输出样例
3
Hint
第11秒后 能力值为4\ 2\ 3\ 14 2 3 1

第22秒后 能力值为4\ 2\ 3\ 14 2 3 1

第33秒后 能力值为5\ 3\ 4\ 15 3 4 1，第22只GT被第33只GT消灭掉了

第44秒后 能力值为6\ 4\ 5\ 26 4 5 2

c_ic​i​​并不是有序的

题解：首先这道题有一个很显然的O(n*logn)O(n∗logn)的做法，直接区间加，求区间最大值即可。 但是此题还有一个O(n)O(n)的做法。我们发现b_1,b_2,...,b_xb​1​​,b​2​​,...,b​x​​都加11就相当于b_{x+1},b_{x+2},...,b_nb​x+1​​,b​x+2​​,...,b​n​​都减11。然后我们可以倒着做，记一下最大值，如果遇到了修改操作，就把最大值减11，然后判断一下这个人会不会被消灭掉，然后再更新一下最大值。
然而我是  二分找c值  放到树状数组中一顿乱搞  最后死在数组范围开小了的坑下，开大点就不会挂终测了，弱鸡
下面我 只给出二分BIT的写法
//meek///#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <stack>

#include <sstream>

#include <vector>

using namespace std ;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

typedef long long ll;

const int N=+;

const int inf = ;

const int mod= ;

int a[N],b[N],c[N];

int C[][N];    int T,n,m;

void update(int x,int index,int val) {

    while(x<N) {

        C[index][x]+=val;

        x+=x&-x;

    }

}

int getsum(int x,int index) {

   int sum=;

   while(x>) {

       sum+=C[index][x];

      x-=x&-x;

   }

return sum;

}

int main() {

    scanf("%d",&T);

    while(T--) {

            mem(C);

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

      for(int i=;i<=n;i++) {

         scanf("%d%d",&a[i],&b[i]);

        }

        for(int i=;i<=m;i++) {

            scanf("%d",&c[i]);

        }

        int tmp0=;

        int tmp1=;

        sort(c+,c+m+);

        for(int i=;i<=n;i++) {

            if(a[i]==) {

                tmp0++;

                int t=lower_bound(c+,c+m+,i)-c;

                b[i]+=(m-t+);

                update(b[i],,);

            }

            else {tmp1++;

                int t=lower_bound(c+,c+m+,i)-c;

                b[i]+=(m-t+);update(b[i],,);

            }

        }

        int ans=;

        for(int i=;i<=n;i++) {

            if(a[i]==) {

                int t=getsum(b[i],);

                if(tmp1-t) ans++;

                //cout<<t<<endl;

                tmp0--;

                update(b[i],,-);

             }

             else {

               int t=getsum(b[i],);

                if(tmp0-t) ans++;

                //cout<<t<<endl;

                tmp1--;

                update(b[i],,-);

             }

        }

        cout<<n-ans<<endl;

    }

    return ;

}

代码

 

相关文章