P5288 [HNOI2019]多边形
Solution
-
先进行大量的模拟。
-
最终所有线段的端点均为点 \(n\)。
-
第一问答案为 \((n - 1 - 与 n 相连的线段数量)\)。
-
可以把线段看成节点，将原图转为若干棵二叉树组成的森林。
这里只建那些不与点 \(n\) 相连的 非边 线段。
-
原操作可以看作是
splay中的rotate操作。如果是对根操作，相当于删掉根节点拆成两棵树，此时第一问答案减一。
易知第一问答案为所有建出来的点的数量。
-
第二问答案相当于对每棵树自上往下删使得最终只剩若干个单点（凸边形的边）的方案数。
具体地，如果有两棵树 \(u, v\)，考虑将答案 \(\times \frac{(sz_u + sz_v)!}{sz_u! sz_v!}\)（相当于全排一次后分别把两棵树的内部顺序固定），然后再递归下去类似地更新方案数。这个算法对一棵树的子树内部合并以及多棵树的方案总计都适用。
-
修改需要分类讨论：
- 修改的是一棵树的根节点，第一问减一，更新相对简单。
- 修改的不是一棵树的根节点，第一问不变，这时可借助
rotate的初末状态图更新答案。
合并与撤销合并还是有点细节的。
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define lowbit(x) x & (-x)
#define PII pair<int, int>
#define MP make_pair
#define VI vector<int>
#define VII vector<int>::iterator
#define EB emplace_back
#define SI set<int>
#define SII set<int>::iterator
#define QI queue<int>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
int inc(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
Sqr(x), k >>= 1;
}
return res;
}
const int N = 1e5 + 5;
int fac[N], facinv[N];
void preprocess()
{
fac[0] = facinv[0] = 1;
for(int i = 1; i < N; ++i)
fac[i] = mul(fac[i - 1], i);
facinv[N - 1] = qwqmi(fac[N - 1]);
for(int i = N - 2; i >= 1; --i)
facinv[i] = mul(facinv[i + 1], i + 1);
}
int op;
int n, Q, cnt, ans = 1;
int sz[N], fath[N], ls[N], rs[N];
vector<int> ed[N];
map<PII, int> mp; // 给边标号
void add(int a, int b)
{
ed[a].EB(b);
ed[b].EB(a);
}
// (撤销)合并操作序列
int cal(int x, int y)
{
return mul(fac[x + y], mul(facinv[x], facinv[y]));
}
int calinv(int x, int y)
{
return mul(facinv[x + y], mul(fac[x], fac[y]));
}
void dfs(int &x, int l, int r, int fa)
{
if(l + 1 == r)
return;
x = ++cnt;
fath[x] = fa;
mp[MP(l, r)] = x;
int mid = *(--lower_bound(ed[l].begin(), ed[l].end(), r));
dfs(ls[x], l, mid, x);
dfs(rs[x], mid, r, x);
sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
Mul(ans, cal(sz[ls[x]], sz[rs[x]]));
}
void print(int x, int y)
{
if(!op) printf("%d\n", x);
else printf("%d %d\n", x, y);
}
int main()
{
preprocess();
scanf("%d", &op);
scanf("%d", &n);
for(int i = 1; i < n; ++i)
add(i, i + 1);
add(1, n);
for(int i = 1; i <= n - 3; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
add(a, b);
}
for(int i = 1; i <= n; ++i)
sort(ed[i].begin(), ed[i].end());
for(int i = 0; i < (int)ed[n].size() - 1; ++i)
{
int root = 0;
dfs(root, ed[n][i], ed[n][i + 1], 0);
Mul(ans, cal(cnt - sz[root], sz[root]));
}
print(cnt, ans);
scanf("%d\n", &Q);
while(Q--)
{
int a, b;
scanf("%d %d", &a, &b);
int x = mp[MP(a, b)];
int res = ans;
if(!fath[x])
{
Mul(res, calinv(cnt - sz[x], sz[x]));
Mul(res, calinv(sz[ls[x]], sz[rs[x]]));
Mul(res, cal(cnt - sz[x], sz[ls[x]]));
// Mul(res, cal(cnt - sz[rs[x]], sz[rs[x]])); // Wrong!!!
Mul(res, cal(cnt - sz[x] + sz[ls[x]], sz[rs[x]])); // 先合并谁无所谓
print(cnt - 1, res);
}
else
{
int f = fath[x];
Mul(res, calinv(sz[ls[f]], sz[rs[f]]));
Mul(res, calinv(sz[ls[x]], sz[rs[x]]));
Mul(res, cal(sz[f] - sz[x] - 1, sz[rs[x]]));
Mul(res, cal(sz[f] - sz[ls[x]] - 1, sz[ls[x]]));
// 本来旋转方向是需要讨论的，即先合并谁对答案有影响(可以推一下，本质是因为先合并的那一坨大小要加一)，
// 但由于 a < b < c < d 的限定，下面这种情况不可能发生，即只能先合并 rs[x]，再合并 ls[x]
// Mul(res, cal(sz[f] - sz[x] - 1, sz[ls[x]]));
// Mul(res, cal(sz[f] - sz[rs[x]] - 1, sz[rs[x]]));
print(cnt, res);
}
}
return 0;
}