题意:
有n只糖糖,排成一排,第i只糖糖能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有另外一组排在他前面的糖糖。此外有发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.问第n秒后还剩几只糖糖?
思路:
刚开始想到的是纯暴力,但是根据数据范围必然会t。所以需要进一步优化。
首先我们先思考第i只糖糖存活的条件:假设第i只糖糖在编号为0的队伍里,经过发功之后,排在第i只糖糖的后面的编号为1的糖糖的能力值都小于它,那么他一定会存活。此外,排在i前面的糖糖发功对于彼此之间的能力差值是没有任何影响的(同时加上一个数,差值不变)。所以说,我们只需要从后面往前面扫描,并且维护两队的能力最大值即可。
具体实现方式分为两步:
1>实现发功后能力值加1:根据题干“第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1”,所以说排在前面的糖糖的能力值提升的次数是最多的,故此,我们可以用反向前缀和来存储能力的提升值。
2>实现两个数组的维护:因为糖糖只会消灭排在他之前的糖糖,而排在他后面的即使比他的能力值低也还可以存活,所以我们选择从后面遍历每个糖糖的存活情况,以编号为0的为例,我们需要判断当前该糖糖的能值是否大于等于已经出现过的编号为1的糖糖的能力值的最大值,如果大于,则编号为0的糖糖可以存活,否则死亡。接着我们需要维护编号为0的糖糖的能力值的最大值。
Ac代码:

const int num=5e4+5;

struct ndoe
{
    int id,b;
}a[num];

int f[num];//存的是反向的前缀和

int main()
{
    int t,m,n;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        memset(f,0,sizeof(f));//注意要跟新前缀和
        int ans=0;
        for(int i=1;i<=n;i++) cin>>a[i].id>>a[i].b;
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            f[x]++;
        }//在第x时刻发功,能力值+1

        int m0=-1,m1=-1;
        for(int i=n;i>=1;i--)
        {
            f[i]+=f[i+1];//反向前缀和
            a[i].b+=f[i];//最终能力值
            if(a[i].id==0)
            {
                if(a[i].b>=m1) ans++;//判断是否满足生存条件
                m0=max(m0,a[i].b);//最大值的维护
            }
            else
            {
                if(a[i].b>=m0) ans++;
                m1=max(m1,a[i].b);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}