CF1956F Nene and the Passing Game 题解

题目链接

点击打开链接

题目解法

首先答案为连边之后连通块的个数

把限制中的 \(i,j\) 分开，则 \(i,j\) 能传球当且仅当 \(i+l_i\le j-l_j\) 且 \(j-r_j\le i+r_i\)
这是一个二维偏序的形式
先考虑怎么暴力做，考虑将 \((i+l_i,0),\;(i-l_i,1)\) 排序，然后按顺序加入

1. 如果碰到操作 \((i+l_i,0)\)，就把 \(i+r_i\) 加入 \(set\)
2. 如果碰到操作 \((i-l_i,1)\)，就把所有 \(set\) 中 \(\ge i-r_i\) 的人都与 \(i\) 合并

如何优化这个过程？
考虑优化连边数量
一个发现是若 \(set\) 中的两人 \(x,y\)，满足 \(x_r+x<y+r_y\) 且 \(x,y\) 连通，则 \(x\) 没有保留的必要，理由显然
那么我们每一次碰到 \((...,1)\) 操作时，把除了最大的且需要合并的人都删除即可

时间复杂度 \(O(n\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
typedef tuple<int,int,int> tup;
const int N=2000010;
int l[N],r[N],fa[N];
bool vis[N];
tup event[N<<1];
#define fi first
#define se second
set<pii> S;
int gfa(int x){ return x==fa[x]?x:fa[x]=gfa(fa[x]);}
void merge(int x,int y){ fa[gfa(x)]=gfa(y);}
void work(){
    S.clear();
    int n;read(n);
    F(i,1,n) read(l[i]),read(r[i]);
    int len=0;
    F(i,1,n) event[++len]={i-l[i],1,i},event[++len]={i+l[i],0,i};
    sort(event+1,event+len+1);
    F(i,1,n) fa[i]=i;
    F(i,1,len){
        auto [t,type,x]=event[i];
        if(!type) S.insert({r[x]+x,x});
        else if(!S.empty()&&(*S.rbegin()).fi>=x-r[x]){
            pii rec=*S.rbegin();
            while(!S.empty()&&(*S.rbegin()).fi>=x-r[x]) merge(x,(*S.rbegin()).se),S.erase(*S.rbegin());
            S.insert(rec);
        }
    }
    F(i,1,n) vis[gfa(i)]=1;
    int ans=0;F(i,1,n) ans+=vis[i],vis[i]=0;
    printf("%d\n",ans);
}
int main(){
    int T;read(T);
    while(T--) work();
    return 0;
}