题面:
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.
现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。
题解:
仔细观察'发功'这一操作可以发现,每次都是加当前位置之前的人的B[i],而我们的操作顺序也是如此,并且每个人只能攻击他前面的人,所以这些'发功'操作是不分先后顺序的,那么我们就可以预处理出来所有人的新B[i]
考虑如何求这个答案,可以知道,如果一个人能存活下来,那么条件一定是,他后面的另一组的人中B[i]全都比他小,所以我们从后往前O(n)扫一下,并且维护两组人的最大B[i]值就可以啦~
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define mkp make_pair #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 3e5 + 6; const LL inf = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} LL inv(LL x){return qp(x,mod-2);} //head int _,n,m,a[maxn],b[maxn],c[maxn],d[maxn]; int main(){ for(scanf("%d",&_);_;_--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i],&b[i]); } for(int i=1;i<=m;i++){ scanf("%d",&c[i]); d[1]++;d[c[i]+1]--; } int s=0; for(int i=1;i<=n;i++) s+=d[i],b[i]+=s,d[i]=0; d[n+1]=0; int mx0=0,mx1=0,ans=0; for(int i=n;i>=1;i--){ if(a[i]){mx1=max(mx1,b[i]); if(b[i]>=mx0) { ans++; } } else {mx0=max(mx0,b[i]); if(b[i]>=mx1){ ans++; } } //cout<<mx0<<','<<mx1<<','<<ans<<endl; } printf("%d\n",ans); } }