CF1895E 题解

· · 题解

显然的，如果对方出了一张牌，那么自己一定要出在比这张牌防御值的大的牌中，防御值最大的牌。

如果不是，那么对手所可以接着出的牌就可能变多，那么这显然不优。

所以我们按照攻击值从小到大排序，然后预处理出后缀最大值和其出现位置，然后对于每张牌二分找到对手攻击力比这张牌防御力大的区间，然后找到防御力的最大值，将这两张牌连边。

这样就会构造出一个有向图，然后如果一个点的出度是 0，那么这个点必胜。

然后进行一次 dfs，因为一个点最多有一条出边，所以这个点的胜负状态就是他所连向的这个点的反面状态。

那么我们就能统计出必胜节点和必输节点，然后用总数减去必胜与必输的节点就是平局的节点数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,d[600005],amax[600005],bmax[600005],posa[600005],posb[600005],ans[600005],vis[600005];
vector<int> ve[600005];
struct nd{
    int x,y;
    friend bool operator<(const nd&a,const nd&b){
        return a.x<b.x;
    }
}a[600005],b[600005];
void dfs(int u){
    if(vis[u])return;
    vis[u]=1;
    for(int v:ve[u]){
        dfs(v);
        ans[u]=-ans[v];
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i].x;
        for(int i=1;i<=n;i++)cin>>a[i].y;
        cin>>m;
        for(int i=1;i<=m;i++)cin>>b[i].x;
        for(int i=1;i<=m;i++)cin>>b[i].y;
        for(int i=1;i<=n+m;i++)ve[i].clear(),d[i]=ans[i]=vis[i]=0;
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        amax[n+1]=bmax[m+1]=INT_MIN;
        for(int i=n;i;i--){
            if(amax[i+1]<a[i].y)amax[i]=a[i].y,posa[i]=i;
            else amax[i]=amax[i+1],posa[i]=posa[i+1];
        }
        for(int i=m;i;i--){
            if(bmax[i+1]<b[i].y)bmax[i]=b[i].y,posb[i]=i;
            else bmax[i]=bmax[i+1],posb[i]=posb[i+1];
        }
        for(int i=1;i<=n;i++){
            int aa=upper_bound(b+1,b+m+1,nd{a[i].y,0})-b;
            if(aa!=m+1){
                ve[i].emplace_back(posb[aa]+n);
                d[i]++;
            }
        }
        for(int i=1;i<=m;i++){
            int bb=upper_bound(a+1,a+n+1,nd{b[i].y,0})-a;
            if(bb!=n+1){
                ve[i+n].emplace_back(posa[bb]);
                d[i+n]++;
            }
        }
        for(int i=1;i<=n+m;i++)if(!d[i])ans[i]=1;
        for(int i=1;i<=n+m;i++)if(!vis[i])dfs(i);
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++)if(ans[i]==1)ans1++;else if(ans[i]==-1)ans2++;
        cout<<ans1<<" "<<n-ans1-ans2<<" "<<ans2<<"\n";
    }
    return 0;
}