【每日一题】糖糖别胡说，我真的不是签到题目 题解

Solution

题意规定 第i只糖糖可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖
考虑从后往前推, 维护两个组的最大值
因为还有发功的情况, 我们考虑用后缀和表示, 因为对于每个点i发功
1, 2......., i都会加1, 因此要从后面往前推
如果当前的糖糖能力值小于另一个组别的最大值, 那么它就会被消灭
然后我们一直更新这两个最大值

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e6 + 5;
const ll mod = 1e9 + 7;
const int DEG = 30;
const double PI = acos(-1.0);
const double eps = 1e-12;
const ll inf = 1e18;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
struct node{
  ll x, y;
}a[N];
int main(){
  int t;
  cin >> t;
  while(t--){
    int n, m;
    cin >> n >> m;
    vector<int> pre(n + 10, 0);
    for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    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], a[i].y += pre[i];
    ll ans = 0;
    ll maxz0 = -1, maxz1 = -1; // 0组 和 1组 最大的
    for(int i = n; i >= 1; i--){
      if(a[i].x == 0){
        if(a[i].y < maxz1){ // 会被消灭
          ans++;
        }
        maxz0 = max(a[i].y, maxz0);
      }
      else if(a[i].x == 1){
        if(a[i].y < maxz0){ // 会被消灭
          ans++;
        }
        maxz1 = max(maxz1, a[i].y);
      }
    }
    cout << n - ans << "\n"; // 总的减去会被消灭的
  }
  return 0;
}