[CF 297E]Mystic Carvings解题报告

题意

有一块圆形浮冰,其边缘上有2n(n<=10^5)个顶点。这些顶点两两配对,共n对,每对顶点之间有曲线相连(可以理解为冰面上的纹路)。有6只熊,它们是3对情侣,要选择6个顶点打洞。要求:
①每对情侣打的两个洞必须是配对顶点,中间有曲线连接。
②每对情侣之间的距离相等。x和y的“距离”是指,沿着浮冰边缘从x走到y,最少需要经过的熊洞数量+1。
例如:

左边这张图可以,右边这张图不行。
图中,1~16为顶点,线代表配对的顶点,AB是一对情侣,CD是一对,EF是一对。
左边图中,C到D的距离为1(经过0个熊洞),A到B的距离为2,E到F的距离为2,故不行。右图中,A到B,C到D,E到F的距离都是1,可行。
求总的打洞方案数。如果两个方案中打洞的集合相同,就认为这两个方案相同(并不考虑哪个洞是谁的)。

分析

这道题的抽象模型颇为有趣。可以发现,只有如下两种可能:

第一种是三对熊洞的连线两两交叉,第二种是三对熊洞的连线两两均不交叉。

如果把每条曲线对应成一个点,若两条曲线交叉则在所对应的两点间连红边,否则连蓝边,那么我们就得到了一个含n个节点的完全图G。可以发现,第一种方案对应G中的一个红色三角形,第二种方案对应G中的一个蓝色三角形。

我们现在试图去求G中的纯色三角形个数a。“纯色三角形”并不好求,但可以将问题转化为求“非纯色三角形”的个数b,而三角形共有C(n,3)个,所以纯色三角形个数就是C(n,3)-b。

那怎么算“非纯色三角形”个数呢?可以看到,每个“非纯色三角形”必然有两个“异色角”。“异色角”是指一个角的两条边一红一蓝,如图:

左边的角就是一个异色角。黑边的颜色未定。若为红,则下面的角是异色角,若为蓝,则上面的角是异色角。总之一定有两个异色角。

于是现在只需要计算异色角的个数c,则b=c/2,a=C(n,3)-c/2.

怎么计算呢?

假设第i条曲线连接了li和ri两个点(li<=ri)。假设有pi条曲线和它交叉(即连出了pi条红边),那么就有qi=n-1-pi条曲线和它不交叉(即连出qi条蓝边),则G中以它为顶点的异色角个数就是pi*qi。

这pi条和它交叉的曲线都满足:一端在区间[li,ri]内,一端在区间[li,ri]之外。不妨称之为“和区间[li,ri]交叉”。假设我们知道了pi,那我们就能O(1)计算出有多少条曲线和[li-1,ri]交叉(讨论li-1配对点是否在区间内即可),同理也能计算出和[li+1,ri],[li,ri-1],[li,ri+1]交叉的曲线数量。

因此我们可以用分块莫队算法求出所有pi和qi,这样我们就算出了异色角个数c,从而算出纯色三角形个数a。

但是到此并未结束,因为“纯色三角形”还包含这种情况:


中间那对熊之间的距离是2,两边两对熊之间的距离都是1,不合法。

这种情况对应于一个蓝色三角形,但并不合法,需要减掉。

计算这种方案数的方法也简单:在分块莫队时再计算一个值si:两端点都在[li,ri]内(显然不与区间[li,ri]交叉)的曲线数量(包含(li,ri)本身)。那么,两端点都在[li,ri]外,不与[li,ri]交叉的曲线数自然就是ti=n-si-pi,以[li,ri]为上图中红线的方案数量为(si-1)*ti。(之所以-1是要扣掉(li,ri)这条曲线)。

设这种方案数为d,那么总的答案就是a-d。

这样就完美解决了问题。

代码

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int SIZE=200010;
LL N,Bsize;
int match[SIZE];
class Curve{
public:
	int l,r;
};
bool operator < (const Curve &a,const Curve &b){
	if(a.l/Bsize==b.l/Bsize) return a.rC[i].l) try_add(--nowl);
		while(nowrC[i].r) try_del(nowr--);
		diff_cnt+=now_cross*(N-1-now_cross);
		wrong_pure+=(now_inner-1)*(N-now_inner-now_cross);
	}
	LL tri_cnt=all_tri-diff_cnt/2;//纯色三角形数目
	tri_cnt-=wrong_pure;
	cout<>N;
	Bsize=sqrt(2*N+1.0);
	int a,b;
	for(int i=1;i<=N;i++){
		scanf("%d%d",&a,&b);
		if(a>b) swap(a,b);
		C[i]=(Curve){a,b};
		match[a]=b;match[b]=a;
	}
	sort(C+1,C+1+N);
}
int main(){
	//freopen("t1.in","r",stdin);
	init();
	work();
	return 0;
}

最后贴张图:




熊:我萌吗?

(大声告诉我,图中坦克有几对负重轮?)


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注