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

题意

n只糖糖分为两组，每只糖糖有一个能力值b[i]。第i秒时，第i只糖糖可以消灭排在他前面且和他不是一组的糖糖。娇姐可以法攻m次，每次发功给定时间t，第t秒后b[1]...b[t]的值都加1。问第n秒后还剩几只糖糖。

思路

理解题意理解了好一会~ ~ 。主要困难点在于m次发功操作，我们可以讨论下发功操作带来的影响。对于一次在第t秒的发功操作，并不会改变前t个糖糖的相对大小，只可能改变前t个糖糖和后面糖糖的相对大小。那么我们可不可以在开始的时候就把b[1]..b[t]先加上1呢？答案是肯定的（参考前面）。这样我们就可以先算出糖糖的最后的能力（可以差分处理），在从后往前处理，判定糖糖会不会被消灭，更新两个组中糖糖的最大能力值。

复杂度

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 10;

int val[2];
int a[maxn], b[maxn], d[maxn];

int main()
{
    int T, n, m;
    for(cin >> T; T--; ){
        cin >> n >> m;

        memset(d, 0, sizeof d);
        val[0] = val[1] = 0;
        for(int i = 1; i <= n; i++){
            cin >> b[i] >> a[i];
        }

        for(int i = 0; i < m; i++){
            int k;
            cin >> k;
            d[0]++; d[k + 1]--;
        }

        for(int i = 1; i <= n; i++){
            d[i] += d[i - 1]; 
            a[i] = a[i] + d[i];
        }

        int ans = n;
        for(int i = n; i >= 1; i--){

            if(a[i] < val[1 - b[i]]){
                ans--;
            }
            val[b[i]] = max(val[b[i]], a[i]);

        }
        cout << ans << endl;
    }


    return 0;
}