题解：P11329 [NOISG 2022 Finals] Towers

· · 题解

可以想到一种有点傻的建造方案，对于 x 坐标相同的所有城市，只用在 y 坐标最小或最大的城市建塔，这样最多有两座塔楼的 x 坐标相同，但 y 坐标的限制还不满足，同一个 y 坐标可能有很多塔。

另一种有点傻的建造方案是，对于 y 坐标相同的所有城市，只用在 x 坐标最小或最大的城市建塔，这样 y 坐标的限制满足了，同一个 x 坐标又可能有很多塔。

把这两种方案综合一下，可以先对所有 x 坐标建上至多两座塔，然后考虑 y 坐标的限制，如果一个 y 坐标上有很多塔，保留 x 最小最大的塔后，这一行的塔都能满足条件，这时可以把夹在中间的塔 y 坐标向内收缩，确保此时满足 x 坐标的限制。不断处理塔太多的 y 坐标，最终可以得到合法方案，用 set 维护每个 y 坐标上的塔即可。

每个城市只会被 set 加入、删除 O(1) 次，总时间复杂度 O(n\log n)。 ::::info[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,x,y,mx,lx[N],rx[N];
map<pair<int,int>,int>mp;
vector<int>l[N],tmp;
bool chs[N];
set<int>st[N];
queue<int>q;
void add(int x,int y){
    st[y].insert(x);
    //cout<<"add "<<x<<" "<<y<<" "<<st[y].size()<<endl;
    if(st[y].size()>2) q.push(y);
}
void del(int x,int y){
    //cout<<"del "<<x<<" "<<y<<endl;
    st[y].erase(x);
}
void solve(){
    while(!q.empty()){
        int now=q.front();q.pop();
        if(st[now].size()<=2) continue;
        auto it1=st[now].begin(),it2=st[now].end();
        it1++,it2--;
        tmp.clear();
        for(auto it=it1;it!=it2;it++) tmp.push_back(*it);//这里提前存一下，不然对set修改时it可能错乱
        //cout<<"solve "<<now<<endl;
        for(int x:tmp){
            if(lx[x]==rx[x]) del(x,now),rx[x]=-1;
            else if(l[x][rx[x]]==now) del(x,now),rx[x]--,add(x,l[x][rx[x]]);
            else if(l[x][lx[x]]==now) del(x,now),lx[x]++,add(x,l[x][lx[x]]);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        mx=max(mx,max(x,y));
        l[x].push_back(y);
        mp[{x,y}]=i;
    }
    for(int i=1;i<=mx;i++){
        if(!l[i].size()) continue;
        sort(l[i].begin(),l[i].end());
        lx[i]=0,add(i,l[i][0]);
        if(l[i].size()>1) rx[i]=l[i].size()-1,add(i,l[i].back());
        else rx[i]=lx[i];
    }
    solve();
    for(int i=1;i<=mx;i++){
        if(lx[i]>rx[i]||!l[i].size()) continue;
        //cout<<i<<":"<<lx[i]<<" "<<rx[i]<<endl;
        chs[mp[{i,l[i][lx[i]]}]]=1;
        chs[mp[{i,l[i][rx[i]]}]]=1;
    }
    for(int i=1;i<=n;i++) cout<<chs[i];
    return 0;
}

:::: ::::info[附一组小样例]

in:
25
1 1
1 2
1 3
1 4
1 5
2 1
2 2 
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5
4 1
4 2
4 3
4 4
4 5
5 1
5 2
5 3
5 4
5 5
out:
1000101010001000101010001

::::