题解：P10230 [COCI 2023/2024 #4] Lepeze

题意

给定一个正 $n$ 边形的三角剖分，一次操作指删去三角剖分的一条边再加入另一条边。

查询 $q$ 次，两种查询，一种是进行一次操作，另一种是询问让三角剖分的边全部与点 $x$ 相连时的最少操作数及其操作方案数。

思路

首先注意到每次操作实际上是选择三角剖分中的一个四边形，将其对角线互换。

那么设未与 $x$ 相连的边为 $p$，则最少操作数即为 $p$（三角剖分原本有 $n-3$ 条边），即每一次操作都可以让一条边与 $x$ 相连。

因为以 $x$ 为顶点的边会划分为多个以 $x$ 为顶点的四边形，如果有四边形的对角线如果没有与 $x$ 相连，就可以用一次操作将对角线换为与 $x$ 相连的边。

如图，一开始有两条边与 $x$ 相连，可以划分出 3 个以 $x$ 为顶点的四边形，那么我们可以通过三次操作将四边形内的对角线互换使得所有边都连向 $x$。

接下来要求的是方案数，注意到如果以每一个三角形为节点，向相邻的三角形连边，图最终会变为一棵树，而每次操作相当于从一个节点向另一个节点走，将他们之间的边连向 $x$。

去掉以 $x$ 为顶点的三角形代表的灰色顶点整个图就变为了一个森林。

由于我们操作必须从以 $x$ 为顶点的四边形向外扩展，所以操作的过程就必须从父节点向子节点走，可以看作一个拓扑序，答案就是求拓扑序的方案。

如图，一种可能的操作方案是 1->2->3->4->5，其中每个节点代表的边是与其父节点相邻的边被操作为与 $x$ 相连的边。

现在就要看如何求拓扑序的方案数了。

已知树的节点数为 $p$，总排列方案为 $p!$，由于每个节点要在其子树节点前，所以每个节点在排列中有 $\frac{1}{sz_i}$ 的概率在其子树节点前，所有节点的限制乘起来就是 $\frac{1}{\prod{sz}}$，总方案是就是 $\frac{p!}{\prod{sz}}$。

现在主要的问题就是求 $\frac{1}{\prod{sz}}$ 了。

注意到一条三角剖分的边实际上将整棵树分为了两部分。

如图，红色边剖出的蓝色部分的子树会对另一侧的三个点作为答案时有 $\frac{1}{sz_i}$ 的贡献，其中 $sz_i=3$，所以当我们增加一条边 $(l,r)$ 时，设一侧有 $a$ 个点，另一侧有 $n-2-a$ 的点，则相当于对 $a$ 个点有 $\frac{1}{n-2-a}$ 的贡献（有 $n-2-a$ 个三角形），反之亦然。

以上就是加边的逻辑，反之就是减边。由于需要维护区间乘和单点差，开一个树状数组即可，时间复杂度 $O(n \log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,q;
ll inv[200010],f[200010],ans[200010];
int lowbit(int x){
	return x&(-x);
}
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
struct N{
	ll tr[200010];
	void add(int x,ll v){
		if(!x)return ;
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]=(tr[i]*v)%mod;
		}
	}
	ll find(int x){
		if(!x)return 1;
		ll ans=1;
		for(int i=x;i;i-=lowbit(i)){
			ans=ans*tr[i]%mod;
		}
		return ans;
	}
	void change(int l,int r,ll v){
		add(l,v);
		add(r+1,qpow(v,mod-2));
		if(l>r)add(1,v);
	}
}tr;
void solve(int x,int y){//加边 
	ans[x]--;ans[y]--;
	int len=(x-y+n)%n-1;
	tr.change(x+1,y-1,inv[len]);
	len=(y-x+n)%n-1;
	tr.change(y+1,x-1,inv[len]);
}
void solve2(int x,int y){//减边 
	ans[x]++;ans[y]++;
	int len=(x-y+n)%n-1;
	tr.change(x+1,y-1,len);
	len=(y-x+n)%n-1;
	tr.change(y+1,x-1,len);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	f[0]=1;
	for(int i=1;i<=n;i++){
		inv[i]=qpow(i,mod-2);
		tr.tr[i]=1;
		f[i]=f[i-1]*i%mod;
		ans[i]=n-3;
	}
	for(int i=1,x,y;i<=n-3;i++){
		cin>>x>>y;
		solve(x,y);
	}
	while(q--){
		int op;
		cin>>op;
		if(op==1){
			int a,b,c,d;
			cin>>a>>b>>c>>d;
			solve2(a,b);
			solve(c,d); 
		}
		else{
			int x;
			cin>>x;
			cout<<ans[x]<<" "<<f[ans[x]]*tr.find(x)%mod<<'\n';
		}
	}
	return 0;
}

题目大意

给定一张三角剖分图，外圈按顺序标号为 $1\sim n$。定义一次操作为删除一条边，再加入一条边得到一个新的三角剖分。

有 $q$ 次修改或询问，每次会进行一次合法操作，或询问一个点 $x$，求最少进行多少次操作使得所有对角线都有共同端点 $x$，以及达到最少操作次数的方案数。

$4 \leq n \leq 2\times 10^5,1 \leq q \leq 2\times 10^5$。

题目分析

首先操作数的下界就是顶点不含 $x$ 的对角线个数，而事实上这个下界很容易取到，所以只需要考虑方案数。

按照这个下界手玩一下，便可以发现新增边的加入顺序会有一定的先后关系，即加入某条边之前必须先加入另一条边：

如图，只有在加入红色边之后才能加入另外两条边，故方案数为 $2$。

以此类推，可以发现其先后顺序会形成一种树形结构，必须按照树的拓扑序进行加边：

其中不交的两棵子树之间互相独立（中间的边会将两边分开），于是方案数即为这棵树的拓扑序个数。

上图为样例二的示意图。可以发现，当初始有对角线顶点包含 $x$ 的时候，这些对角线划分出来的区域互相独立，最终也会形成若干棵树。

而树的拓扑序方案数即为 $\dfrac{n!}{\prod\limits_{i=1}^{n}{siz_i}}$，其中 $siz_i$ 为 $i$ 子树的大小，$n$ 为总节点个数，在题目中的显现即为第一问（最少操作次数）的答案。

考虑如何在原图中快速刻画这棵树。将三角剖分形成的树画出来：

对比发现除去黑点之后，这就是我们想要的树，而黑点就是相邻两个顶点包含 $x$ 的边中间夹成的三角形。证明比较容易，在此省略。

于是现在的主要问题在于如何维护 $\prod\limits_{i}{siz_i}$，修改就相当于删边加边。考虑树上的一个点（非黑点）及其子树，它在原图上其实代表着一段完整圆弧，设其为 $[l,r]$，那么这个子树的大小即为中间剖出来的三角形个数，为 $r-l-1$。而它是非黑点的条件也很简单，即 $[l,r]$ 不能包括 $x$。

现在这道题的做法已经呼之欲出了：对于每条对角线 $(x,y)$，将没被 $x\to y$ 这段圆弧包含的点除以 $len_{x\to y}-1$；将没被 $y\to x$ 这段圆弧包含的点除以 $len_{y\to x}-1$。这是一个区间乘，单点查询问题，使用树状数组即可做到 $\mathcal O((n+q)\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
#define mod 1000000007
ll n,q,jc[200020],jcinv[200020],invv[200020],sum[200020],tree[200020];
il ll lowbit(ll x){
	return x&(-x);
}
il void mdf(ll x,ll v){
	if(v<0) v=-v;
	else v=invv[v];
	while(x<=n){
		tree[x]=tree[x]*v%mod;
		x+=lowbit(x);
	}
}
il ll query(ll x){
	ll res=1;
	while(x){
		res=res*tree[x]%mod;
		x-=lowbit(x);
	}
	return res;
}
il void solve(ll x,ll y,ll t){
	sum[x]-=t;
	ll len=(y-x+n)%n-1;
	swap(x,y);
	x=x%n+1;
	y=(y+n-2)%n+1;
	if(x<=y){
		mdf(x,t*len);
		mdf(y+1,-t*len);
	}
	else{
		mdf(x,t*len);
		mdf(1,t*len);
		mdf(y+1,-t*len);
	}
}
int main(){
	n=read();
	q=read();
	jc[0]=1;
	fr(i,1,n) jc[i]=jc[i-1]*i%mod;
	jcinv[n]=inv(jc[n],mod);
	pfr(i,n-1,0) jcinv[i]=jcinv[i+1]*(i+1)%mod;
	fr(i,1,n) invv[i]=jcinv[i]*jc[i-1]%mod;
	fr(i,1,n) sum[i]=n-3;
	fr(i,1,n) tree[i]=1;
	fr(i,1,n-3){
		ll x=read(),y=read();
		solve(x,y,1);
		solve(y,x,1);
	}
	while(q--){
		ll opt=read();
		if(opt==1){
			ll x=read(),y=read(),xx=read(),yy=read();
			solve(x,y,-1);
			solve(y,x,-1);
			solve(xx,yy,1);
			solve(yy,xx,1);
		}
		else{
			ll x=read();
			pf("%lld %lld\n",sum[x],jc[sum[x]]*query(x)%mod);
		}
	}
}