rt,调了一场。求 hack。做法是并查集,对于每个横坐标维护形成的区间,相邻的就合并。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second
const int N=200005;
int n;
VI poi[N],ids[N];
int area[N<<1],fa[N<<1],tot;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){if(x||y)dbg(x,y);fa[find(x)]=find(y);}
int main()
{
ios::sync_with_stdio(false),cin.tie(nullptr);
// int _;cin>>_;while(_--)
cin>>n;
for(int i=1,x,y;i<=n;i++)cin>>x>>y,poi[x+1].PB(y);
for(int i=1;i<=200002;i++)
{
sort(ALL(poi[i]));
for(int j=0;j<=poi[i].size();j++)
{
int id=0;
if(j&&j<poi[i].size())
{
if(poi[i][j]-poi[i][j-1]==1){ids[i].PB(-1);continue;}
ids[i].PB(id=++tot);
area[tot]=poi[i][j]-poi[i][j-1]-1,fa[tot]=tot;
}
int k=j?lower_bound(ALL(poi[i-1]),poi[i][j-1]+2)-poi[i-1].begin():0;
if(!k&&(id||poi[i-1].empty())){merge(id,0);continue;}
k=max(0,k-1);
while(poi[i-1][k]+1<(j==poi[i].size()?INT_MAX:poi[i][j]))
{
if(k+1==poi[i-1].size()){merge(id,0);break;}
if(poi[i-1][k+1]-poi[i-1][k]>1)merge(id,ids[i-1][k]);
k++;
}
}
}
ll ans=0;
for(int i=1;i<=tot;i++)
if(find(i)!=find(0))ans+=area[i];
cout<<ans;
return 0;
}