即将 AFO 的老年选手

题解 P4737 【[CERC2017]Buffalo Barricades】

2020-10-28 11:22:10


我们首先求出每个栅栏实际包含的牛的数量(也就是不算被后面的栅栏包含的)。

从上往下扫描线,并用 set 维护所有往下的栅栏的横坐标。

  • 如果当前点是牛,我们找到一个最小的 $x\geq$ 它的横坐标的栅栏,则最终这个栅栏包含这头牛;
  • 如果当前点是栅栏,我们把它加入 set 中,然后模拟一遍往左延伸的过程,把编号比它大的连续的一段删掉。

接着求出每个栅栏加入时包含的牛的数量。可以发现,如果 A 包含 B,且 A 加入时间比 B 早,那么 B 的答案要加到 A 中去。可以发现这个东西实际构成一个树形关系,我们只需要从前往后扫,然后把父边断掉,这样子扫到每个点时它的 $size$ 就是答案了。可以直接 LCT 维护。

当然也可以不 LCT,直接倒过来变成加边,就很好用并查集维护了。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=600000+10;

int n,m,ans[N],cnt[N],fa[N];
struct Point { int x,y,t; } p[N];
set<pair<int,int>> S;

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int main() {
    n=read();
    for (int i=1;i<=n;++i) p[i]=(Point){read(),read(),0};
    m=read();
    for (int i=1;i<=m;++i) p[i+n]=(Point){read(),read(),i};
    sort(p+1,p+n+m+1,[](Point a,Point b) {
        return a.y!=b.y?a.y>b.y:a.t>b.t;
    });
    for (int i=1;i<=n+m;++i) {
        if (!p[i].t) {
            auto it=S.lower_bound({p[i].x,0});
            if (it!=S.end()) ++cnt[it->second];
        } else {
            S.insert({p[i].x,p[i].t});
            auto it=S.find({p[i].x,p[i].t});
            if (++it!=S.end()) fa[p[i].t]=it->second;
            while (1) {
                it=S.find({p[i].x,p[i].t});
                if (it==S.begin()) break;
                --it;
                if (it->second>p[i].t) S.erase(it);
                else break;
            }
        }
    }
    for (int i=1;i<=m;++i) f[i]=i;
    for (int i=m;i;--i) {
        ans[i]=cnt[find(i)];
        if (fa[i]) {
            int x=find(i),y=find(fa[i]);
            f[x]=y,cnt[y]+=cnt[x];
        }
    }
    for (int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}