题解：P10763 [BalticOI 2024] Tiles

· · 题解

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

题目分析

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

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

于是可以维护两个 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;
}