题解 | #糖糖别胡说，我真的不是签到题目#

题目考点：前缀和、枚举

题目大意：两组糖糖站一排，顺序任意。遍历这一排时，当前糖糖会消除前面与他不同组而且数值比自己小的糖糖，遍历一个糖糖用时1秒。另外有m次施法，第x秒的施法可使前x个糖糖数值+1，求最后没有被消除的糖糖的个数。

核心思想：设j > i, 若a[ j ] + 收益 > a[ i ]，且a[ j ]、a[ i ]不同组，a[ i ]就会被消除。其中“收益”指的是i到j秒时间内施法的次数

代码：

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 50010;
int t, n, m;
int a[N], b[N], c[N];
int x;
int cnt = 0;

int main()
{
    scanf("%d", &t);
    
    while(t--)
    {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        cnt = 0;
        
        scanf("%d%d", &n, &m);
        
        //输入所需数据
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &a[i], &b[i]);
        while(m--)
            scanf("%d", &x), c[x] ++;
        
        //计算c数组前缀和
        for(int i = n; i ; i--)
            c[i] += c[i+1], b[i] += c[i];  //b[i] + 收益
        
        //遍历维护最大值以及淘汰过程
        int max0 = 0, max1 = 0;
        for(int i = n; i ; i--)
        {
            if(a[i])
            {
                max1 = max(max1, b[i]);
                if(b[i] < max0)cnt++;
            }
            else
            {
                max0 = max(max0, b[i]);
                if(b[i] < max1)cnt++;
            }
        }
        printf("%d\n", n - cnt);
    }
    
    return 0;
}