糖糖别胡说，我真的不是签到题目
糖糖别胡说，我真的不是签到题目
https://ac.nowcoder.com/acm/problem/14583
链接：https://ac.nowcoder.com/acm/problem/14583
来源：牛客网
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
从前，有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
题解：
这道题目真的。。。。。。果然不是签到题。。。。。。
当时写第一遍的时候就直接写到前缀和的基本操作，后面就没（不）有（会）再（写）弄（了）。今天看了别人的题解，照着把后面最有含金量的四行代码补上，换成scanf就ac了。（QAQ这个scanf啊。。。。真的是。。。。。）
下面就是复述了。ai是不是会死取决于后面有没有功力更高的对手aj，我们知道ai和aj的功力和发功对应的前缀和。而然我们已经做好了前缀和，那就发功的影响只需要计算前缀和的差值，也就是b[i-1]-b[j-1]。所以如果ai会被aj杀死，那么a[i]+b[j-1]-b[i-1]<a[j];把i、j移到同一侧，也就是a[i]-b[i-1]<a[j]-b[j-1];又由于我们知道如果不是最强的都能杀死他，那么最强的也一定可以。问题就变得非常简单了，只需要维护两队各自的最强者即可。
代码：
using namespace std;
#include <bits/stdc++.h>
#define int long long
int a[50005][4],b[50005],Max[2];
int inf=0x3f3f3f3f;
signed main (void)
{
int t;cin>>t;
while (t--)
{
memset (a,0,sizeof a);
memset (b,0,sizeof b);
Max[0]=Max[1]=-inf;
int n,m;cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
}
for (int i=1;i<=m;i++)
{
int x;cin>>x;
b[x]++;
}
for (int i=1;i<=n;i++)
{
b[i]+=b[i-1];
cout<<b[i];
}
int cnt=0;
for (int i=n;i>0;i--)
{
int sum=Max[a[i][0]^1];
if (sum<=a[i][1]-b[i-1]) cnt++;
Max[a[i][0]]=max(Max[a[i][0]],a[i][1]-b[i-1]);
}
cout<<cnt<<'\n';
}
}
