NC14583

可以发现，在每次发功后，从1到i都会加1，所以1到i其实他们的大小关系不变，所以我们可以离线做，把所有的发功都做完，然后从后到前进行扫描一遍就可以了。具体的就是用一个累加数组，从后到前，计算每个糖糖最终的b，可以知道，只有后面的糖糖对前面的有影响，所以我们从后到前，因为只有两个组，所以我们只需要记录目前的分别两个组的最大值，看看是否大于当前的b就可以记录最终剩下的值了

#include<bits/stdc++.h>
using namespace std;
int a[50005],b[50005],c[50010],sum[50010],Max[4];
int main()
{
    //freopen("a.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(sum,0,sizeof(sum));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
        int x;
        for(int i=1;i<=m;i++) {scanf("%d",&x);sum[x]++;}
        for(int i=n;i>=1;i--) sum[i]+=sum[i+1];

         Max[0]=0,Max[1]=0;
         int ans=n;
         for(int i=n;i>=1;i--)
         {
             if(Max[a[i]^1]>b[i]+sum[i]) ans--;
             Max[a[i]]=max(b[i]+sum[i],Max[a[i]]);
        }
        printf("%d\n",ans);
    }

    return 0;
}