我觉得你就是一道我签不了到还说自己不是签到题的签到题。orz

题目

题目描述 ：
从前，有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组数据中，糖糖存活的个数。

解析

这道题其实不难，但是需要思考到这道题的特点：
  • 这道题唯一难的地方就是：糖糖的爸爸，娇姐，会发功m次。
由于每次发功，前面的数就会增加，并对他与后面的数比大小产生影响。
所以！这句话反过来说就是：我们就发现后面的数增大，好像不会对和前面的数比大小产生影响。

所以我们就有了思路（虽然我几乎没有）：
  1. 首先用数组保存下每个糖糖的能力值（power）和队伍信息（team）。
  2. 接下来就是发功的问题了我们用简单的将发功，散列在每个位置上，并初始化为1。（magic数组保存）
  3. 根据我们刚刚分析的：发功会对他与后面的数比大小产生影响。所以我们就能得到power[pos] = magic[pos]+……+magic[n]。
    于是我们就可以将这个数组按逆序操作（详细情况看代码）
  4. 得到发功后的power数组，最后就是判断了：判断的特点也是，当前数后面的数只要有大于他的，这个数就会被删除了。
  5. 所以我们就可以这样做：用max_0和max_1实时标记当前数后面的数。（因为要算后面的数的最大值，所以我们还是逆序遍历）。
  6. 因为删除的是另一组的糖糖，所以我们用一个条件判断当前数和另一组最大值的大小就好了。然后比另一组最大值小的记录删除（我们这里用cnt反向记录保留的数）

AC代码 

#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int INF = 0x7fffffff;
const int MAX = 1e5 + 7;
//代码预处理
int power[MAX], team[MAX], magic[MAX];//power为能力值，team为队伍，magic为发功位置

int main() {
    js;
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> team[i] >> power[i];
        memset(magic, 0, sizeof(magic));
        for (int i = 1; i <= m; i++) {
            int pos; cin >> pos;
            magic[pos]++;
        }
        //power，team，magic数组初始化
        for (int i = n; i >= 1; i--) {
            power[i] += magic[i];
            magic[i - 1] += magic[i];
        }
        //逆序遍历使power数组变成发功之后的模样
        int max_0 = -INF, max_1 = -INF;//分别表示已经遍历过的0队和1队中的最大值
        int cnt = 0;
        for (int i = n; i >= 1; i--)
            if (team[i]) {
                if (max_1 < power[i]) max_1 = power[i];
                //确定该组最大值
                if (max_0 <= power[i]) cnt++;
                //比另一组最大值的小的全要删除（大于等于则保留）
            }
            //1队的情况
            else {
                if (max_0 < power[i]) max_0 = power[i];
                //确定该组最大值
                if (max_1 <= power[i]) cnt++;
                //比另一组最大值的小的全要删除（大于等于则保留）
            }
            //0队的情况
        cout << cnt << endl;
    }
    return 0;
}