来源：牛客网

题目描述

从前，有 nnn 只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第 iii 只糖糖会随机得到一个能力值 bib_ibi。从第 iii 秒的时候，第 iii 只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功 mmm 次，第 iii 次发功的时间为 cic_ici，则在第 cic_ici 秒结束后，b1,b2,.....,bcib_1,b_2,.....,b_{c_i}b1,b2,.....,bci都会增加 1.
现在，娇姐想知道在第 nnn 秒后，会有多少只糖糖存活下来。

输入描述: 

第一行只有一个整数 T（T<6）T（T<6）T（T<6），表示测试数据的组数。
第二行有两个整数 n,mn,mn,m。表示糖糖的个数以及娇姐发功的次数。（1≤n≤50000,1≤bi≤10000001 \leq n\leq 50000,1 \leq b_i \leq 10000001≤n≤50000,1≤bi≤1000000）
第三行到 n+2n+2n+2 行,每行有两个整数 ai,bia_i,b_iai,bi,表示第 iii 只糖糖属于那一组以及他的能力值。（0≤ai≤1,1≤bi≤10000000\leq a_i \leq 1,1\leq b_i\leq 10000000≤ai≤1,1≤bi≤1000000）
第 n+3n+3n+3 行到第 n+m+2n+m+2n+m+2 行，每行有一个整数 cic_ici ，表示GTW第 iii 次发功的时间.(1≤ci≤n1\leq c_i \leq n1≤ci≤n)

输出描述: 

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

输入

复制 1 4 3 0 3 1 2 0 3 1 1 1 3 4 
1 
4 3 
0 3 
1 2 
0 3 
1 1 
1 
3 
4

输出

复制 3 
3
本题可以换个角度，糖糖最终是否存活其实取决于后面是否有与之不同组且能力大于它的糖糖，这样只需要从后向前遍历的时候维护一个一组和二组的最大值就可以了。但题目上还会发功导致糖糖的能量值增加，看似是一个麻烦的条件。但由于发功只影响当前和之前的糖糖，也就是说发功的时候计算和发功后再计算是一样的效果。那么只需要先将发功的能量加上后再进行上面的步骤就可以了。

代码： 
#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

struct Tang{
    int tag;
    int av;
    int add = 0;
} tang[50005];

int main() {
    IOS;
    int T, temp;
    cin>>T;
    for (int i=0;i<T;i++) {
        int n, m;
        cin>>n>>m;
        int cnt = n;
        for (int k=0;k<n;k++) {
            cin>>tang[k].tag;
            cin>>tang[k].av;
            tang[k].add = 0;
        }
        //再读入的时候就直接加进去，不影响后续的结果。
        for (int k=0;k<m;k++) {
            cin>>temp;
            //从第一位开始加
            tang[0].add++;
            //从下一位开始恢复
            tang[temp].add--;
        }
        tang[0].av += tang[0].add;
        //求前缀和，求出每个糖糖在增加过后的真实能量值
        for (int k=1;k<n;k++) {
            tang[k].add = tang[k].add+tang[k-1].add;
            tang[k].av += tang[k].add;
        }
        //根据能量值去求糖糖最终是死亡还是存活
        //倒着求其后方0组合1组的最大值
        int max0 = INT_MIN;
        int max1 = INT_MIN;
        for (int k=n-1;k>=0;k--) {
            //先判断当前糖糖是否会死亡
            if (tang[k].tag==0&&tang[k].av<max1) {
                cnt--;
            }
            if (tang[k].tag==1&&tang[k].av<max0) {
                cnt--;
            }
            if (tang[k].tag==0&&tang[k].av>max0) {
                max0 = tang[k].av;
            }
            if (tang[k].tag==1&&tang[k].av>max1) {
                max1 = tang[k].av;
            }
        }
        cout<<cnt<<endl;
    }
    
    return 0;
}