这题,我们只需要分析下一个点可以被另一个点给消除的条件后,我们就可以很简单的处理了~

首先由题,一个点i会被一点j消除的条件当且仅当:

,第j秒时,

我们发现,前两个都是很好判断的,但是最后一个条件就有点烦了,因为我们中间掺杂着若干个加的操作

注意到,每次加时,我们都是把b[1]-b[ci]的点加1。

所以,第j秒时,加的值=加的次数,等于

这个就很简单了,我们可以直接根据c的值做前缀:sum[i]表示第i秒时,一共加了sum[i]次,那么,就有:

第j秒时:j加的次数:,i加的次数:,那么,我们带入式子,就有:

化简一下:

注意到,两边具有对称性,所以,我们设,

那么,我们只需要知道,对于一个点i,是否存在一个j满足:

如果存在,那么这个i就会被消去,否则不会。

对于这个,我们直接倒着扫一遍,每次更新每组的最大值即可~

复杂度:

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N],b[N];
int n,m;
int sum[N];//第i秒加了多少次
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            sum[i]=0;
            scanf("%d%d",&a[i],&b[i]);
        }
        for(int i=1;i<=m;++i){
            int x;
            scanf("%d",&x);
            ++sum[x];
        }
        for(int i=1;i<=n;++i){
            sum[i]+=sum[i-1];
            b[i]-=sum[i-1];
        }
        int ans=n,maxe[2];
        maxe[0]=maxe[1]=-2e9;
        for(int i=n;i;--i){
            if(b[i]<maxe[a[i]^1]){
                --ans;
            }
            maxe[a[i]]=max(maxe[a[i]],b[i]);
        }
        printf("%d\n",ans);
        //一个点j可以消除i,当且仅当:
        //b[j]+sum[j]-sum[j-1]>b[i]+sum[j]-sum[i-1]
        //即:b[j]-sum[j-1]>b[i]-sum[i-1]
        //直接统计即可~
    }
    return 0;
}