糖糖别胡说，我真的不是签到题目-------前缀和（附带难度题目提高版）

对于这道题，如果按照朴素算法来说，第一反应是对于每个位置i的糖糖，处理1 ~ i-1 被消灭的糖糖有哪些，给他们标记，然后最后统计一遍，很显然，这样复杂度很高，不足以通过这道题，所以我们换种处理方法。
先看m次操作，有影响的一定是 ，我们可以维护一个前缀和， 表示第 项前面有几次操作，这样做的意义是什么呢，对于 表示位置 的糖糖比位置 多了几次赋值 的操作。

对于每个位置i的糖糖，我们考虑是否会被击杀，我们可以发现，当且仅当 位置存在和糖糖 不是一队且 的时候，位置 的糖糖才会被击败，将式子移项即可发现， ，所以我们可以维护这个式子的最大值即可，由于是维护 到 的最大值，所以只需要倒着扫描数组即可，计算不能被击败的有几个，输出即可，由于题目限制队伍 ,所以只需要用两个变量维护就行。

#include <cstring>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include<time.h>
#define ll long long
using namespace std;
const int maxn=2e5+10,INF=0x3f3f3f3f;
int B[maxn],Csum[maxn],team[maxn],Max[2];
struct node {
    int Left,Right,val,lazy;
}NODE[maxn<<2];
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        Max[0]=Max[1]=-INF;
        for (int i=1; i<=n; i++) {
            Csum[i]=0;
            scanf("%d%d",&team[i],&B[i]);
        }
        for (int i=1; i<=m; i++) {
            int idx;
            scanf("%d",&idx);
            Csum[idx]++;
        }
        for (int i=1; i<=n; i++) Csum[i]+=Csum[i-1];
        int cnt=0;
        for (int i=n; i>=1; i--) {
            int sum=Max[team[i]^1];
            if (sum<=B[i]-Csum[i-1]) cnt++;
            Max[team[i]]=max(Max[team[i]],B[i]-Csum[i-1]);
        }
        printf("%d\n",cnt);
    }
    return 0;
}

对于队伍数量达到n的情况，我们核心思路还是维护这个式子，只不过不止两个变量维护最大值了，需要n个变量维护每个队伍的最大值，但是如果朴素维护，复杂度也会退化到 ，所以我们开一颗维护最大值的线段树即可，复杂度 ，代码如下：

#include <cstring>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include<time.h>
#define ll long long
using namespace std;
const int maxn=2e5+10,INF=0x3f3f3f3f;
int B[maxn],Csum[maxn],team[maxn];
struct node {
    int Left,Right,val,lazy;
}NODE[maxn<<2];
void build(int l, int r, int idx) {
    NODE[idx].Left=l,NODE[idx].Right=r;
    NODE[idx].lazy=-INF;
    NODE[idx].val=-INF;
    if (l==r) return;
    int m=(l+r)>>1;
    build(l,m,idx<<1);
    build(m+1,r,idx<<1|1);
}
void PushUp(int idx) {
    NODE[idx].val=max(NODE[idx<<1].val,NODE[idx<<1|1].val);
}
void PushDown(int idx) {
    if (NODE[idx].lazy!=-INF) {
        NODE[idx<<1].val=max(NODE[idx<<1].val,NODE[idx].lazy);
        NODE[idx<<1].lazy=max(NODE[idx<<1].lazy,NODE[idx].lazy);
        NODE[idx<<1|1].val=max(NODE[idx<<1|1].val,NODE[idx].lazy);
        NODE[idx<<1|1].lazy=max(NODE[idx<<1|1].lazy,NODE[idx].lazy);
        NODE[idx].lazy=-INF;
    }
}
void Updata(int l, int r, int val, int idx) {
    if (NODE[idx].Left==l&&NODE[idx].Right==r) {
        NODE[idx].lazy=max(NODE[idx].lazy,val);
        NODE[idx].val=max(NODE[idx].val,val);
        return;
    }
    PushDown(idx);
    int m=(NODE[idx].Left+NODE[idx].Right)>>1;
    if (r<=m) Updata(l,r,val,idx<<1);
    else if (l>m) Updata(l,r,val,idx<<1|1);
    else {
        Updata(l,m,val,idx<<1);
        Updata(m+1,r,val,idx<<1|1);
    }
    PushUp(idx);
}
int query(int l, int r, int idx) {
    if (l>r) return -INF;
    if (NODE[idx].Left==l&&NODE[idx].Right==r) {
        return NODE[idx].val;
    }
    PushDown(idx);
    int m=(NODE[idx].Left+NODE[idx].Right)>>1;
    int res;
    if (r<=m) res=query(l,r,idx<<1);
    else if (l>m) res=query(l,r,idx<<1|1);
    else res=max(query(l,m,idx<<1),query(m+1,r,idx<<1|1));
    PushUp(idx);
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,n,1);
        for (int i=1; i<=n; i++) {
            Csum[i]=0;
            scanf("%d%d",&team[i],&B[i]);
            team[i]++;
        }
        for (int i=1; i<=m; i++) {
            int idx;
            scanf("%d",&idx);
            Csum[idx]++;
        }
        for (int i=1; i<=n; i++) Csum[i]+=Csum[i-1];
        int cnt=0;
        for (int i=n; i>=1; i--) {
            int Max=max(query(1,team[i]-1,1),query(team[i]+1,n,1));
            if (Max<=B[i]-Csum[i-1]) cnt++;
            Updata(team[i],team[i],B[i]-Csum[i-1],1);
        }
        printf("%d\n",cnt);
    }
    return 0;
}