糖糖

题目表述不是特别好而且数据没有给全，比如m的数据规模没有给出。

正向的时间复杂度是

后缀数组+差分

实际上影响因子只有最末敌对最大点，也即：如果一个人后面没有比他更大的另一个队伍的人，那么他一定能活下来。

故从后往前看只需要不断锚定最大的点，逐步更新计数即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e6 + 7;
const int N = 50005;
int a[N], b[N], v[N], mx[2], c;
int main() {
    ll n, m, T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        fill(v, v + N, 0);
        for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
        for (int i = 1; i <= m; ++i) cin >> c, ++v[c];
        mx[a[n]] = b[n] + v[n];  //最后一人所属队伍的最大值
        mx[!a[n]] = 0;           //另一队所属队伍的最大值
        int cnt = 1;             //最后一个人一定能活下来
        for (int i = n - 1; i; --i) {
            v[i] += v[i + 1];
            if (v[i] + b[i] >= mx[!a[i]]) ++cnt;
            mx[a[i]] = max(mx[a[i]], v[i] + b[i]);  //更新所属队伍最大值
        }
        cout << cnt << endl;
    }
    return 0;
}