链接：https://ac.nowcoder.com/acm/problem/14583 来源：牛客网

题目描述

从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。

为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,…,bci都会增加1.

现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。

输入描述:

第一行只有一个整数T（T<6），表示测试数据的组数。 第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。（1<=n<=50000,1<=bi<=1000000） 第三行到n+2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。（0<=ai<=1,1<=bi<=1000000） 第n+3行到第n+m+2行，每行有一个整数ci，表示GTW第i次发功的时间.(1<=ci<=n)

输出描述:

总共T行，第i行表示第i组数据中，糖糖存活的个数。 示例1 输入

1 4 3 0 3 1 2 0 3 1 1 1 3 4

输出

3

【想说的】这道题目看上去好像很复杂的样子，输入也给的其奇怪，但是仔细体会，其实题意还是很好懂得。但是思路一开始确实很难想到除暴力外的算法。仔细思考那个增加战斗力的过程本质是给一个区间的数都加上1，这想省时间，不就使用差分嘛。再仔细思考，这个增加过程，从前往后，会略显复杂，但是，如果想到只要他能死，无论是加魔法还是从后往前都没有关系（和他这个加魔法的方式有关），这点还是蛮难想到的。然后就是顺便就复习一下差分啦~

题解

#include <bits/stdc++.h> using namespace std; struct tt{ int id; int bi; }t[50005]; int p[50005]; int main() { int ttt; scanf("%d",&ttt); while(ttt--) { memset(p,0,sizeof p); int n,m; scanf("%d%d",&n,&m); t[0].bi=0; for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); t[i].id=a; t[i].bi=b; p[i]=t[i].bi-t[i-1].bi; } for(int i=0;i<m;i++) { int g; scanf("%d",&g); p[1]++; p[g+1]--; } for(int i=1;i<=n;i++) { t[i].bi=t[i-1].bi+p[i]; } int maxx1=-1; int maxx2=-1; int sum=0; for(int i=n;i>0;i--) { if(t[i].id==1) { maxx2=max(maxx2,t[i].bi); if(t[i].bi>=maxx1) sum++; } else{ maxx1=max(maxx1,t[i].bi); if(t[i].bi>=maxx2) sum++; } } printf("%d\n",sum); } return 0; }