自动搬运

查看原文

来自洛谷，原作者为

	wangyizhi 昨夜西风凋碧树。独上高楼，望尽天涯路。

搬运于2025-08-24 23:00:59，当前版本为作者最后更新于2025-06-27 14:21:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

挺好想但是非常难写的一道题。。。

题目分析

显然我们可以扫描线。在从左往右扫的过程中若不合法的情况则输出此时的答案。

题目给的条件相当于：此时扫描到的任意一条线段长为偶数；一条线段加进来与踢出去的位置奇偶性相同。

于是可以维护两个 set<pair<int,int>>，分别存在偶数下标和奇数下标加进来的线段。但在加入时，可以将其与边上的线段合并。此时可以维护奇数线段的个数。删除同理。若加完或删完后奇数线段的个数大于 $0$，则不合法。在加入前我们还需一些特判。这条线段不能在两个 set 中都有能覆盖的线段，也不能被包含在奇偶性不同的那个 set 的线段中，否则不合法。至于如何判断一条线段时加还是删，也可以采取类似的方法，若在 set 中的线段能把它包含，就删除，否则加入。

然后来统计答案。若此时两个 set 其中一个为空，说明不会出现交错的情况，否则当前不行。若奇偶性不同的 set 为空，则把答案更新为当前坐标减一；若奇偶性相同的 set 为空，则把答案更新为当前坐标。需要注意的是，这些操作应在加入删除线段之前之后都做一遍。

于是就做完了。显然 $O(n \log n)$。

AC Code

跑得还挺快的啊。

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//bool Mst;
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=2e5+5;
vector<pii> seg[N];
int b[N],bc,cnt;
set<pii> st[2];
int len(pii x){return (x.second-x.first)&1;}
bool check(set<pii> &st,pii x)
{
	auto it=st.lower_bound(x);
	if(it!=st.end()&&it->first<=x.first&&it->second>=x.second) return 1;
	if(it==st.begin()) return 0;
	it--;
	if(it->first<=x.first&&it->second>=x.second) return 1;
	return 0;
}
bool in(set<pii> &st,pii x)
{
	auto it=st.lower_bound(x);
	if(it!=st.end()&&it->first>=x.first&&it->second<=x.second) return 1;
	if(it==st.begin()) return 0;
	it--;
	if(it->first>=x.first&&it->second<=x.second) return 1;
	return 0;
}
void insert(set<pii> &st,pii x)
{
	auto it=st.lower_bound(x);
	if(it!=st.end())
	{
		if(it->first==x.second) x.second=it->second,cnt-=len(*it),st.erase(*it);
	}
	it=st.lower_bound(x);
	if(it!=st.begin())
	{
		it--;
		if(it->second==x.first) x.first=it->first,cnt-=len(*it),st.erase(*it);
	}
	cnt+=len(x),st.insert(x);
}
void erase(set<pii> &st,pii x)
{
	auto it=st.lower_bound(x);
	if(it==st.end()||it->first>x.first) it--;
	if(it->first<x.first)
	{
		pii y={it->first,x.first};
		cnt+=len(y),st.insert(y);
	}
	if(it->second>x.second)
	{
		pii y={x.second,it->second};
		cnt+=len(y),st.insert(y);
	}
	cnt-=len(*it),st.erase(*it);
}
pii p[N];
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int n,m,ans=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second,b[++bc]=p[i].first;
	sort(b+1,b+bc+1),bc=unique(b+1,b+bc+1)-b-1;
	for(int i=1;i<=n;i++) p[i].first=lower_bound(b+1,b+bc+1,p[i].first)-b;
	p[0]=p[n];
	for(int i=1;i<=n;i++)
	{
		if(p[i].first==p[i-1].first)
		{
			int le=min(p[i].second,p[i-1].second),ri=max(p[i].second,p[i-1].second);
			seg[p[i].first].push_back({le,ri});
		}
	}
	for(int i=1;i<=bc;i++)
	{
		int x=b[i]&1;
		if(st[x].empty()) ans=b[i]-1;
		if(st[!x].empty()) ans=b[i];
		for(pii e:seg[i])
		{
			if((in(st[0],e)&&in(st[1],e))||check(st[!x],e))
			{
				cout<<ans<<"\n";
				return 0;
			}
			if(check(st[x],e)) erase(st[x],e);
			else insert(st[x],e);
		}
		if(st[x].empty()) ans=b[i]-1;
		if(st[!x].empty()) ans=b[i];
		if(cnt) break;
	}
	cout<<ans<<"\n";
	return 0;
}