https://www.luogu.org/problemnew/show/P5288
题解
非常有意思的一道题。
首先观察可得最终的不能继续操作的状态一定是所有边都连向(n)的。
我们还可以发现最优的操作一定是依次将每条边调整为连向(n)的。
所以最小的操作次数就是(n-3-)连向(n)的边的条数。
我们假设现在拿着一个多边形，我们把n这个点作为这个多边形的顶端，那么每条边都会有一个管辖区间就是它下面的点的集合。
这些区间只会有包含关系，我们可以把它整成一棵树。
于是我们发现，最优情况下每次操作一定是将一个根进行操作。
那么如果要求合法操作序列的话就把这颗树搞出来，(dfs)一遍用插板法就能算出来了。
对于修改，我们可以手动模拟一下，发现这个和(splay)的(rotate)差不多，那么就按照(rotate)的过程把贡献算一下就好了。
代码
#include<bits/stdc++.h>
#define N 200009
#define mm make_pair
#define ls ch[cnt][0]
#define rs ch[cnt][1]
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int ans1,n,W,size[N],ch[N][2],fa[N],rt[N],tot;
ll ans2,jie[N],ni[N];
map<pair<int,int>,int>mp;
vector<int>vec[N];
inline ll rd(){
ll x=0;char c=getchar();bool f=0;
while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?-x:x;
}
inline ll power(ll x,ll y){
ll ans=1;
while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}
return ans;
}
inline ll C(int n,int m){return jie[n]*ni[m]%mod*ni[n-m]%mod;}
inline ll _C(int n,int m){return ni[n]*jie[m]%mod*jie[n-m]%mod;}
inline ll calc(int x,int y){return C(x+y,y);}
inline ll _calc(int x,int y){return _C(x+y,y);}
inline bool ge(int x){return ch[fa[x]][1]==x;}
inline void build(int &cnt,int l,int r,int _fa){
if(r-l<=1)return;
cnt=++tot;
fa[cnt]=_fa;
size[cnt]=1;
mp[mm(l,r)]=cnt;
int p=*lower_bound(vec[r].begin(),vec[r].end(),l+1);
build(ch[cnt][0],l,p,cnt);build(ch[cnt][1],p,r,cnt);
size[cnt]+=size[ls]+size[rs];
ans2=ans2*calc(size[ls],size[rs])%mod;
}
inline void print(){
if(!W){printf("%d
",ans1);}
else printf("%d %lld
",ans1,ans2);
}
inline void print(int ans1,ll ans2){
if(!W){printf("%d
",ans1);}
else printf("%d %lld
",ans1,ans2);
}
inline void yu(int n){
jie[0]=1;
for(int i=1;i<=n;++i)jie[i]=jie[i-1]*i%mod;
ni[n]=power(jie[n],mod-2);
for(int i=n-1;i>=0;--i)ni[i]=ni[i+1]*(i+1)%mod;
}
int main(){
W=rd();
n=rd();
yu(2*n);
ans1=n-3;
int x,y;
for(int i=1;i<=n-3;++i){
x=rd();y=rd();
if(x>y)swap(x,y);
if(y==n)ans1--;
vec[x].push_back(y);
vec[y].push_back(x);
}
ans2=1;
for(int i=1;i<n;++i)vec[i].push_back(i+1),vec[i+1].push_back(i);
vec[1].push_back(n);vec[n].push_back(1);
for(int i=1;i<=n;++i)sort(vec[i].begin(),vec[i].end());
int sum=0;
for(int i=0;i<vec[n].size()-1;++i){
build(rt[i],vec[n][i],vec[n][i+1],0);
ans2=ans2*calc(size[rt[i]],sum)%mod;
sum+=size[rt[i]];
}
print();
int m=rd();
while(m--){
x=rd();y=rd();
if(x>y)swap(x,y);
int id=mp[mm(x,y)];
int _ans1=ans1;
if(!fa[id])_ans1--;
ll _ans2=ans2;
if(fa[id]){
int f=fa[id],o=ge(id);
_ans2=_ans2*_calc(size[ch[id][0]],size[ch[id][1]])%mod;
_ans2=_ans2*_calc(size[ch[f][0]],size[ch[f][1]])%mod;
_ans2=_ans2*calc(size[ch[id][o^1]],size[ch[f][o^1]])%mod;
_ans2=_ans2*calc(size[ch[id][o]],size[ch[id][o^1]]+size[ch[f][o^1]]+1)%mod;
}
else{
_ans2=_ans2*_calc(size[ch[id][0]],size[ch[id][1]])%mod;
_ans2=_ans2*_calc(sum-size[id],size[id])%mod;
_ans2=_ans2*calc(sum-size[id],size[ch[id][0]])%mod;
_ans2=_ans2*calc(sum-size[id]+size[ch[id][0]],size[ch[id][1]])%mod;
}
print(_ans1,_ans2);
}
return 0;
}