题解：P10230 [COCI 2023/2024 #4] Lepeze
qdl66666666
·
·
题解
P10230题解
题目链接
题意
给定 n 个顶点的多边形，n-3 条对角线形成一个三角剖分（顾名思义 n-3 条对角线将多边形分成了一个个三角形）。
有两种操作：
1.删除一条对角线，并添加新的一条（算一次操作）。
2.问此时将所有对角线的一端移到 x 上的最小操作次数和其方案数。
注意三角剖分和操作 2 时不能让当前的对角线有交。
突破点
从 sub2 中受到启发，发现最小操作次数就是端点不在 x 上的对角线条数。
简单证明一下：对于一条对角线 (p,q)，它存在于两个三角形中，所对的点分别记为 x,r。我们可以删除 (p,q)，添加 x,r 使得对角线的一端变为 x，而我们每次可以选择不被其他对角线包含的一条操作。至于一端在 x 上的对角线，我们不进行操作显然更优。
第一步转化
经过最小操作次数的启发，我们可以发现操作的一般顺序。
我们将所有对角线看作不经过 x 的弧的形式，则：
- 任意两条弧要么不交要么包含（根据三角剖分的性质）。
- 每次一定选择一条极大的弧（不被其他弧包含的弧），满足操作中对角线无交。
- 一条弧至多直接包含两条弧（无用）。
第二步转化
将所有弧看作点，将弧与弧之间的包含关系映射为树上的父子关系（大弧为父亲），就得到了一个二叉树形结构。
结合我们上一步的操作顺序，我们就是每次处理一个父亲节点，然后将它的儿子加入到待处理集合中。这样我们的操作方案数就是一个树上拓扑序数，因为弧与弧之间可能无交，也就是可能有很多棵树形成的森林，操作方案数为森林拓扑序数量。
有个经典结论，森林拓扑序数量为 \frac{n!}{\prod sz_{i}}。
设弧为 $(l,r)$，则包含数量就是 $(r - l - 1)$，只需计算所有不经过 $x$ 的弧的弧长-1的乘积。
所以我们记录每个点上连接的对角线条数 $ind[i]$，最小操作次数就是 $n - 3 - ind[x]$，方案数就是不经过 $x$ 的弧的条数除以所有弧的包含总数和。
## 第三步优化
考虑优化复杂度，用树状数组维护 $mul[i]$，表示不经过 $i$ 号点的对角线/弧包含总数和（也就是 $\prod sz_{i}$ 这部分）。维护对角线就是维护对角线所对的两条弧上的点：具体的，添加一条对角线就是进行区间乘，删除对角线就是区间乘以逆元。
区间修单点查利用差分思想转为单点修前缀查，$[l,r]$ 的区间乘就是 $l$ 上乘，$r+1$ 上乘逆元。
快速幂算逆元，预处理阶乘，树状数组维护，复杂度 $O((n+q)\log n)$。
## 细节
本题的区间为环形区间，要注意 $l,r,1,n$ 的关系。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
template<typename TY>
inline void read(TY &s){
ll x = 0,f = 1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
s = x * f;
}
int n,q;
int ind[N];
ll qpow(ll a,ll b,ll p){
ll res = 1;
while(b){
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res % p;
}
inline ll inverse(ll x){
return qpow(x,MOD-2,MOD);
}
inline int dist(int x,int y){
if(x < y) return y - x;
else return y - x + n;
}
ll mul[N],fac[N];
inline void modify(int x,ll v){
for(int i=x;i<=n;i+=lowbit(i)) mul[i] = mul[i] * v % MOD;
}
inline ll query(int x){
ll res = 1;
for(int i=x;i;i-=lowbit(i)) res = res * mul[i] % MOD;
return res;
}
inline void M(int l,int r,ll v){
if(l > r) return;
modify(l,v); modify(r+1,inverse(v));
}
inline void change(int x,int y,ll v){
if(x < y){
M(x+1,y-1,v);
}
else{
M(x+1,n,v);
M(1,y-1,v);
}
}
int main(){
read(n); read(q);
int a,b;
fac[0] = 1;
for(int i=1;i<=n;i++){
fac[i] = fac[i - 1] * i % MOD;
mul[i] = 1;
}
for(int i=1;i<=n-3;i++){
read(a); read(b);
ind[a]++; ind[b]++;
change(a,b,dist(b,a)-1);
change(b,a,dist(a,b)-1);
}
int c,d,opt;
while(q--){
read(opt);
if(opt == 1){
read(a); read(b); read(c); read(d);
ind[a]--; ind[b]--; ind[c]++; ind[d]++;
change(a,b,inverse(dist(b,a)-1));
change(b,a,inverse(dist(a,b)-1));
change(c,d,dist(d,c)-1);
change(d,c,dist(c,d)-1);
}
else{
read(a);
cout << (n - 3 - ind[a]) << " " << (fac[n-3-ind[a]]) * inverse(query(a)) % MOD << "\n";
}
}
return 0;
}
```