【每日一题0421】枚举，后缀和，思维

https://ac.nowcoder.com/acm/problem/14583
题目：一共两组糖，第i只糖可以消灭掉所有排在他前面的和他不是同一组的且值小于他的数；第i秒会让前ci个值加1；问最后存活多少个糖。

这个题有意思的点就是题面给你展示的是动态给前i个增加1；但实际上这个动态增加和一次性加上去结果是一样的。因为两个都增加1 大小关系是不变的。用每个糖最后他的值判断能不能存活就行了。
也就是说第i只糖能否存活取决于后面有没有比他大且不是同一个组的
从后往前 维护两个组最大值就可以了；增加1的操作用后缀和来维护就可以
如果当前的糖能力值小于另一个组别的最大值, 那么它就会被消灭

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 5;
struct node {
    ll grp, val;  // grp:组别 val：值
} num[N];
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        ll pre[50010] = {0};
        for (int i = 1; i <= n; i++)
            cin >> num[i].grp >> num[i].val;
        for (int i = 1; i <= m; i++) {
            int x;
            cin >> x;
            pre[x]++;
        }
        for (int i = n; i >= 1; i--)
            pre[i] += pre[i + 1], num[i].val += pre[i];
        ll ans = 0;
        ll maxz0 = -1, maxz1 = -1;  
        for (int i = n; i >= 1; i--) {
            if (num[i].grp == 0) {
                if (num[i].val < maxz1) {  //被消灭
                    ans++;
                }
                maxz0 = max(num[i].val, maxz0);
            } else if (num[i].grp == 1) {
                if (num[i].val < maxz0) {  
                    ans++;
                }
                maxz1 = max(maxz1, num[i].val);
            }
        }
        cout << n - ans << "\n";
    }
    return 0;
}