思路：一个O(n)O(n)的做法。我们发现b_1,b_2,...,b_xb1,b2,...,bx都加11就相当于b_{x+1},b_{x+2},...,b_nbx+1,bx+2,...,bn都减11。然后我们可以倒着做，记一下最大值，如果遇到了修改操作，就把最大值减11，然后判断一下这个人会不会被消灭掉，然后再更新一下最大值。
1 #define cn(i,p,q) for(int i=p;i<=q;i++)
2 #define cn1(i,p,q) for(int i=p;i>=q;i--)
3 #define pr(x) printf("%d\n",x)
4 #define prr(x) printf("%d",x)
5 #define prrr(x) printf(" %d",x)
6 #define sc(x) scanf("%d",&x)
7 #define scc(x) scanf("%lf",&x)
8 #define pr1(x) printf("%.2f\n",x)
9 #include<stdio.h>
10 #include<algorithm>
11 #include<iostream>
12 #include<string.h>
13 #include<stdlib.h>
14 #include<math.h>
15 int maxx[2][1];//两种情况分别表示两个不同队中从后往前时最大值
16 typedef struct pp
17 {
18 int xx;
19 int yy;
20 int flag;
21 } ss;
22 const int N=1e6+10;
23 ss a[N];
24 int b[N];//记录在何时放技能的次数
25
26 using namespace std;
27 int main(void)
28 {
29 int n,m,l,k,s;
30 sc(n);
31 int x;
32 int y;
33 while(n--)
34 {
35 sc(x);
36 sc(y);
37 memset(b,0,sizeof(b));
38 memset(maxx,0,sizeof(maxx));
39 int qq=0;
40 cn(i,1,x)
41 {
42 int vp;
43 int va;
44 sc(vp);
45 sc(va);
46 a[i].xx=vp;
47 a[i].yy=va;
48 a[i].flag=0;
49 }
50 cn(i,1,y)
51 {
52 sc(k);
53 b[k]++;
54 }
55 maxx[a[x].xx][0]=a[x].yy;//最后一个先初始化最大
56 cn1(i,x-1,1)
57 {
58 cn(j,0,1)
59 {
60 maxx[j][0]-=b[i];//减放技能所减少的
61 }
62 int zz=(a[i].xx+1)%2;
63 if(a[i].yy<maxx[zz][0])
64 {
65 qq++;
66 }//如果当前的小于另一组的最大值这个点就会消失
67 maxx[a[i].xx][0]=max(maxx[a[i].xx][0],a[i].yy);//更新同一组的最大值
68
69 }
70 int zk=x-qq;
71 pr(zk);
72 }
73 return 0;
74 }