luogu3415 祭坛

先二分答案转化成判定问题。

考虑拿一根扫描线从 \(x=0\) 扫到 \(x=n\)，每次移动扫描线更新每个位置它上面的点数和下面的点数，这样可以确定在当前的扫描线上哪些位置对于 \(y\) 轴方向是合法的。对于 \(x\) 轴方向合法的点应该处的范围可以直接算出来，树状数组维护。

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

int n, uu, vv, siz[100005], upp[100005], loo[100005], ans1, ans2, c[100005];

vector<int> vx[100005];

int lb(int x){

	return x&-x;

}

void add(int pos, int val){

	if(pos==0)	c[0]+=val,pos=n+n;

	for(int i=pos; i<=n; i+=lb(i))	c[i] += val;

}

int query(int pos){

	int re=0;

	for(int i=pos; i; i-=lb(i))	re += c[i];

	return re+c[0];

}

bool check(int k){

	int num=0, l, r;

	for(int i=0; i<=n; i++)	upp[i] = 0, loo[i] = siz[i], c[i]=0;

	for(int i=1; i<=n; i++){

		int qwqq=vx[i-1].size();

		for(int j=0; j<qwqq; j++){

			int t=vx[i-1][j];

			bool isok=(upp[t]>=k)&&(loo[t]>=k);

			upp[t]++;

			if(!isok && upp[t]>=k && loo[t]>=k)	add(t, 1);

		}

		qwqq=vx[i].size();

		bool flag=qwqq>=2*k;

		if(flag)	l=vx[i][k-1]+1, r=vx[i][vx[i].size()-k]-1;

		for(int j=0; j<qwqq; j++){

			int t=vx[i][j];

			bool isok=(upp[t]>=k)&&(loo[t]>=k);

			loo[t]--;

			if(isok && !(upp[t]>=k && loo[t]>=k))	add(t, -1);

			if(isok && flag && t>=l && t<=r)	num--;

		}

		if(!flag || l>r)	continue;

		num += query(r) - query(l-1);

	}

	if(!num)	return false;

	ans1 = k; ans2 = num;

	return true;

}

int main(){

	cin>>n;

	for(int i=1; i<=n; i++){

		scanf("%d %d", &uu, &vv);

		vx[uu].push_back(vv);

		siz[vv]++;

	}

	for(int i=0; i<=n; i++)	sort(vx[i].begin(), vx[i].end());

	int l=0, r=n, mid;

	while(l<=r){

		mid = (l + r) >> 1;

		if(check(mid))	l = mid + 1;

		else	r = mid - 1;

	}

	cout<<ans1<<endl<<ans2<<endl;

	return 0;

}

巴特西

luogu3415 祭坛

最新文章

热门文章