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

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存活下来。$

输入描述

第一行只有一个整数 $第三到n+2n+2行，每行有两个整数a_i,b_ia​i​​,b​i​​，表示第ii只GT在哪个组和他的能力值 (0leq a[i]leq 1,1leq 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次发功的时间。1leq c[i]leq n1≤c[i]≤n$

输出描述

总共

输入样例

输出样例

Hint

第 $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=1050000+100;
const int inf = 99999999;
const int mod= 1000000007;

int a[N],b[N],c[N];
int C[2][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=0;
   while(x>0) {
       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=1;i<=n;i++) {
         scanf("%d%d",&a[i],&b[i]);
        }
        for(int i=1;i<=m;i++) {
            scanf("%d",&c[i]);
        }
        int tmp0=0;
        int tmp1=0;
        sort(c+1,c+m+1);
        for(int i=1;i<=n;i++) {
            if(a[i]==0) {
                tmp0++;
                int t=lower_bound(c+1,c+m+1,i)-c;
                b[i]+=(m-t+1);
                update(b[i],0,1);
            }
            else {tmp1++;
                int t=lower_bound(c+1,c+m+1,i)-c;
                b[i]+=(m-t+1);update(b[i],1,1);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) {
            if(a[i]==0) {
                int t=getsum(b[i],1);
                if(tmp1-t) ans++;
                //cout<<t<<endl;
                tmp0--;
                update(b[i],0,-1);
             }
             else {
               int t=getsum(b[i],0);
                if(tmp0-t) ans++;
                //cout<<t<<endl;
                tmp1--;
                update(b[i],1,-1);
             }
        }
        cout<<n-ans<<endl;
    }
    return 0;
}

代码