Buffalo Barricades 题解

这题的难点在于某一头牛可能被多个农名占有。怎么处理呢？

我们仔细分析一下就会发现，每一个农名的篱笆最多被一个篱笆直接包含，所以我们把这些之间包含的农名之间连上边，最终形成的是一个森林。

但是我们一开始卡在了：一个农名包含某一个农名的篱笆，只有这个农名来的更早，才能得到包含的这个农名的牛，这其实就变成了一个三维偏序问题，不太容易解。

但其实我们可以从后往前将这些边加回来就可以了。

用dsu维护。

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n;
vector<pair<mp,int> > event;
bool cmp(pair<mp,int>  A,pair<mp,int> B){if(A.FIR.SEC!=B.FIR.SEC){return A.FIR.SEC>B.FIR.SEC;}return A.SEC>B.SEC;
}
int ans[300000+20];
set<mp> barrier;
int fa[300000+20],con[300000+20];
int root(int x){return fa[x]=(fa[x]==x? x:root(fa[x]));
}
int main(){scanf("%d",&n);rb(i,1,n){int x,y;scanf("%d%d",&x,&y);event.PB(II(II(x,y),0));}	int m;scanf("%d",&m);rb(i,1,m){int x,y;scanf("%d%d",&x,&y);event.PB(II(II(x,y),i));}sort(ALL(event),cmp);for(auto eve:event){if(eve.SEC==0){auto ite=barrier.lower_bound(II(eve.FIR.FIR,-INF));if(ite==barrier.end()) continue;ans[ite->SEC]++;}else{int x,t;x=eve.FIR.FIR;t=eve.SEC;auto ite=barrier.upper_bound(II(x,t));if(ite!=barrier.end())con[eve.SEC]=ite->SEC;if(ite!=barrier.begin()){ite--;while(ite->SEC>t){bool break_=(ite==barrier.begin());set<mp> :: IT nex;if(!break_){nex=--ite;ite++;}barrier.erase(ite);if(break_) break;ite=nex;}	}barrier.insert(II(x,t));}}rb(i,1,m)fa[i]=i;vector<int> ans_;rl(i,m,1){ans_.PB(ans[i]);if(con[i]){fa[i]=root(con[i]);
//			cout<<i<<'-'<<root(i)<<' '<<con[i]<<endl;ans[root(i)]+=ans[i];}}reverse(ALL(ans_));for(auto it:ans_) printf("%d\n",it);return 0;
}