[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;
}

最后贴张图：




熊：我萌吗？

（大声告诉我，图中坦克有几对负重轮？）


发表回复

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