USACO open 2024 银组 T2

EnofTaiPeople · 2024-03-25 11:51:40 · 题解

考虑如何快速通过银组。

首先题目没有按逆时针顺序给定栅栏，考虑建出这个环。

分析性质，将对于横坐标相同，纵坐标第 2k-1 和 2k 小的点之间连边，另一边同理，这样使图形成一个循环链表。

注意要对于每个横纵坐标开一个 std::set 来存储。

接下来，对于每个询问点，尝试在循环链表中插入这些点，使用 set 求出前驱后继即可。

然后断环成链，对于每次询问更改差分数组，最后再做一遍前缀和即可，时间 O((n+P)\log(n+P))，空间 O(n+P)：

int T,n,K,m,ct,mp[N],to[N],pr[N],sf[N];
#define MP(x) lower_bound(mp+1,mp+m+1,x)-mp
struct dat{
    int x,y;
    void mc(){
        x=MP(x),y=MP(y);
    }
    int dst(dat &p){
        return abs(mp[x]-mp[p.x])+abs(mp[y]-mp[p.y]);
    }
}d[N];
set<pair<int,int> >tx[N],ty[N];
int upd(int x,int y){
    auto it=tx[x].lower_bound(mkp(y,0));
    int p;
    if(it!=tx[x].end()){
        if(it->first==y)return it->second;
        p=it->second;
        if(d[pr[p]].x==x&&d[pr[p]].y<=y){
            d[++ct]={x,y};
            to[pr[ct]=pr[p]]=ct;
            pr[to[ct]=p]=ct;goto lc1;
        }
        if(d[to[p]].x==x&&d[to[p]].y<=y){
            d[++ct]={x,y};
            pr[to[ct]=to[p]]=ct;
            to[pr[ct]=p]=ct;goto lc1;
        }
    }
    it=ty[y].lower_bound(mkp(x,0));
    p=it->second;
    if(d[pr[p]].y==y&&d[pr[p]].x<=x){
        d[++ct]={x,y};
        to[pr[ct]=pr[p]]=ct;
        pr[to[ct]=p]=ct;goto lc1;
    }
    if(d[to[p]].y==y&&d[to[p]].x<=x){
        d[++ct]={x,y};
        pr[to[ct]=to[p]]=ct;
        to[pr[ct]=p]=ct;goto lc1;
    }
    lc1:tx[x].emplace(y,ct);
    ty[y].emplace(x,ct);
    return ct;
}
struct D2{
    int x,y,l,r;
    void mc(){x=upd(MP(x),MP(y)),y=upd(MP(l),MP(r));}
}d2[N];
ll v[N];
vector<int>lk[N];
void dfs(int x){
    for(int y:lk[x])
        if(x!=to[y]&&!pr[y]){
            pr[to[x]=y]=x;
            if(!to[y])dfs(y);
        }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int i,j,k,l,r,x,y,z;ll v1,v2;
    cin>>T>>n;
    for(x=1;x<=n;++x){
        cin>>l>>r;
        mp[++m]=l,mp[++m]=r;
        d[x]={l,r};
    }
    for(i=1;i<=T;++i){
        cin>>x>>y>>l>>r;
        mp[++m]=x,mp[++m]=y;
        mp[++m]=l,mp[++m]=r;
        d2[i]={x,y,l,r};
    }
    sort(mp+1,mp+m+1),m=unique(mp+1,mp+m+1)-mp-1;
    for(x=1,ct=n;x<=n;++x){
        d[x].mc();
        tx[d[x].x].emplace(d[x].y,x);
        ty[d[x].y].emplace(d[x].x,x);
    }
    for(x=1;x<=m;++x){
        l=0;
        for(auto &p:tx[x]){
            r=p.second;
            if(l){
                lk[l].push_back(r);
                lk[r].push_back(l);l=0;
            }else l=r;
        }
        l=0;
        for(auto &p:ty[x]){
            r=p.second;
            if(l){
                lk[l].push_back(r);
                lk[r].push_back(l);l=0;
            }else l=r;
        }
    }
    dfs(1);
    // for(x=1;x<=ct;++x)printf("x:%d pr:%d to:%d\n",x,pr[x],to[x]);puts("");
    // return 0;
    for(i=1;i<=T;++i)d2[i].mc();
    for(x=to[1];;x=to[x]){
        v[x]=v[pr[x]]+d[x].dst(d[pr[x]]);
        // printf("%d ",x);
        if(x==1)break;
    }
    for(i=1;i<=T;++i){
        l=d2[i].x,r=d2[i].y;
        if(v[l]>v[r])swap(l,r);
        // printf("l:%d r:%d\n",l,r);
        if((v[r]-v[l])*2>v[1]){
            ++sf[to[1]],--sf[to[l]];
            ++sf[r];
        }else{
            ++sf[l];
            if(r!=1)--sf[to[r]];
        }
    }
    for(x=to[to[1]];;x=to[x]){
        sf[x]+=sf[pr[x]];
        if(x==1)break;
    }
    for(x=1;x<=n;++x)printf("%d\n",sf[x]);
    return 0;
}