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

题意：

有n个糖糖，每个糖糖都有一个组别0或1，以及它的能力值。
在第i秒的时候，第i个糖糖就会干掉前面能力值比它小且非同组的糖糖 有m次发功，每次发功可以让前i个糖糖能力值+1

解法：

枚举暴力 从后往前遍历，依次更新糖糖的最大值，小于别组最大能力值的糖糖必然会干掉
问题在于如果解决不断发功更新的糖糖的能力值。仔细思考可以发现一个神奇的点，我们可以一口气把所有的发功都给使用完，而且不会从后往前遍历不会影响我们想要得到的结果（可以手动模拟一遍）。
所以利用差分获得发功后的能力值后，从后往前遍历一遍即可。

时间复杂度

O（n）

#include <algorithm>
#include <cstring>
using namespace std;

const int N = 5e4 + 7;

int a[N], b[N], c[N];
int n, m;

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i] >> b[i];
        for (int i = 1; i <= m; i++)  // 差分
        {
            int x;
            cin >> x;
            c[1]++, c[x + 1]--;
        }
        for (int i = 1; i <= n; i++)
        {
            c[i] += c[i - 1];
            b[i] += c[i];
        }
        
        int m0 = 0, m1 = 0, res = 0;
        for (int i = n; i >= 1; i--)
        {
            if (a[i] == 0)
            {
                m0 = max(m0, b[i]); // 更新当前最大能力值
                if (b[i] < m1) res++;
            }
            else if (a[i] == 1)
            {
                m1 = max(m1, b[i]);  // 更新当前最大能力值
                if (b[i] < m0) res++;
            }
        }
        
        cout << n - res << endl;
    }
    return 0;
}