时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。

为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.

现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。

输入描述:

第一行只有一个整数T（T<6），表示测试数据的组数。

第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。（1<=n<=50000,1<=bi<=1000000）

第三行到n+2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。（0<=ai<=1,1<=bi<=1000000）

第n+3行到第n+m+2行，每行有一个整数ci，表示GTW第i次发功的时间.(1<=ci<=n)

输出描述:

总共T行，第i行表示第i组数据中，糖糖存活的个数。

输入

1 4 3 0 3 1 2 0 3 1 1 1 3 4

输出

3

思路

这道题初看条件非常复杂，但其实只需要按照时间考虑一遍就可以了

因为每一只糖糖都会影响它前面的糖糖，所以从后往前考虑，记录两队各自目前最大的糖糖，前面的糖糖如果小于对方最大值就一定会被消灭。

还有很烦的一点是娇姐要发功（这位父亲的名字好奇怪），会影响计算，所以将每一秒受娇姐影响的次数记录下来。

核心算法：差分

因为要记录每一秒影响的次数，但是不能每一次都循环考虑，所以使用差分数组 c 记录。

每一个b[i]都要减去c[i - 1]，也就是减去它消灭时前面的糖糖能力值增加的数量。

*代码中使用了team^1，由于team只能为0或1，异或的作用就是将0转换为1，将1转换为0，表示对方的队伍。

代码

#include<bits/stdc++.h>
using namespace std;
int T, n, m, a[50007], b[50007], c[50007], MAX[5], sum, cnt, team;
int main(){
    cin >> T;
    while(T--){
        sum = cnt = 0;
        MAX[0] = MAX[1] = -10000007;
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            cin >> a[i] >> b[i];
            c[i] = 0;
        }
        for(int i = 1; i <= m; i++){
            int x;
            cin >> x;
            c[x]++;
        }
        for(int i = 1; i <= n; i++)
            c[i] += c[i - 1], b[i] -= c[i - 1];
        for(int i = n; i >= 1; i--){
            sum = 0;
            if(a[i] == 1) team = 1;
            else team = 0;
            sum = MAX[team ^ 1];
            if(sum <= b[i]) cnt++;
            MAX[team] = max(MAX[team], b[i]);
        }
        cout << cnt << endl;
    }
    return 0;
}

啾咪！

End.