Question

个人排成一排，每个人有能力值，分为两组或。
第秒的时候，第个人可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的人。
有次发功，第次发功的时间为，则在第秒结束后，都会增加1.
第n秒后，会有多少人存活下来。

Solution

堆 模拟 差分
跟着时间模拟，直接暴力为会TLE，因为时间最大为5e4，考虑优化，发现可以建立两个小根堆来比较，这样每个元素最多入队出队一次，然后考虑如何模拟发功，如果是让前面已经入堆的+1，会很麻烦，这里利用差分的思想，前面的不加，让后面的减就是了，这样只用维护一个base表示差分前缀和。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 5e4 +5;

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

void solve(){
    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[x]++;
    }
    priority_queue<int, vector<int>, greater<int> >q1,q2;
    int base=0;
    for(int i=1;i<=n;i++){
        if(a[i]){ 
            q1.push(b[i]+base);
            while(!q2.empty()&&q2.top()<b[i]+base) q2.pop();
        }
        else {
            q2.push(b[i]+base);
            while(!q1.empty()&&q1.top()<b[i]+base) q1.pop();
        }
        while(c[i]>0){
            base--;
            c[i]--;
        }
    }
    cout<<q1.size()+q2.size()<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}