【考试总结】2021-01-18
点点的圈圈
题目中保证了两个圆包含或者相离，由此想到使用树形 \(\rm DP\) 来进行最终答案的计算
剩下的问题就是建树的加速，直觉上是使用 \(\rm KD-Tree\) 来维护给定的二维平面
不难发现，在保证只存在包含/相离关系后，半径较长的圆 \(A\) 过一个半径较小的圆 \(B\) 的圆心就等价于 \(A\) 包含 \(B\)
按照半径排序后，每个圆在树上找那些被包含的圆心并连边即可，最后将自己加入 \(\rm KD-Tree\)
按照惯例，树要一开始就建满，而满树 树高是 \(\log n\) 的，那么在插入一个点时直接跳父链进行 “子树内点的数量的更新” 即可
我的估价函数时判断点到四个边的距离，但是需要特判半径较小的圆来跑暴力，对于这种问题的另一个解决方式是进行点的旋转
Code Display
const int N=1e5+10;
int dp[N],w[N],rt,n;
vector g[N];
inline void dfs(int x){
for(auto t:g[x]) dfs(t),dp[x]+=dp[t];
ckmax(dp[x],w[x]);
return ;
}
int ls[N],rs[N],siz[N],mx[N][2],fa[N],mn[N][2],pos[N][2];
inline void push_up(int x){
rep(i,0,1){
mx[x][i]=mn[x][i]=pos[x][i];
if(ls[x]){
ckmax(mx[x][i],mx[ls[x]][i]);
ckmin(mn[x][i],mn[ls[x]][i]);
}
if(rs[x]){
ckmax(mx[x][i],mx[rs[x]][i]);
ckmin(mn[x][i],mn[rs[x]][i]);
}
} return ;
}
struct node{int p[2],id;}nds[N];
inline int build(int l,int r,int cur){
if(r>1;
nth_element(nds+l,nds+mid,nds+r+1,[&](const node &a,const node &b){return a.p[cur],int>mp;
inline void ins(int x,int v){
int tmp=x;
while(tmp){
siz[tmp]+=v;
tmp=fa[tmp];
} return ;
}
inline ll calc(ll x,ll y){return (X-x)*(X-x)+(Y-y)*(Y-y);}
inline void connect(int p){
if(!siz[p]) return ;
if(Xmx[p][0]||Y>mx[p][1]||YR&&min(abs(Y-mn[p][1]),abs(Y-mx[p][1]))>R) return ;
}
if((Xmx[p][0])&&(Y>mx[p][1]||Y=calc(pos[p][0],pos[p][1])&&siz[p]-siz[ls[p]]-siz[rs[p]]){
g[nowid].pb(p);
ins(p,-1);
}
if(ls[p]) connect(ls[p]); if(rs[p]) connect(rs[p]);
return ;
}
struct Node{int x,y,r,id;}a[N];
signed main(){
n=read();
rep(i,1,n){
pos[i][0]=a[i].x=read(); pos[i][1]=a[i].y=read();
a[i].r=read(); w[i]=read();
a[i].id=nds[i].id=i; nds[i].p[0]=a[i].x; nds[i].p[1]=a[i].y;
mp[{a[i].x,a[i].y}]=i;
}
rt=build(1,n,0);
sort(a+1,a+n+1,[&](const Node &a,const Node &b){return a.r=calc(j,k)){
if(mp.count({j,k})){
int id=mp[{j,k}];
if(!(siz[id]-siz[ls[id]]-siz[rs[id]])) continue;
g[nowid].pb(id);
ins(id,-1);
}
}
}
}
}else{
connect(rt);
}
ins(a[i].id,1);
}
rep(x,1,n) for(auto t:g[x]) in[t]++;
int ans=0;
rep(i,1,n) if(!in[i]) dfs(i),ans+=dp[i];
print(ans);
return 0;
}
点点的计算
可以通过对列观察得到下降幂形式，再使用吸收恒等式可以得到 \(T_{i,j}=i\binom{i-1}{j-1}\)，处理组合数时只对修改过的指数次幂取 \(\max\) 就能做到平方复杂度
根据定义 \(T_{i,j}=\frac{T_{i-1,j-1}T_{i,j-1}}{T_{i,j-1}-T_{i-1,j-1}}\)，设 \(a=T_{i-1,j-1},b=T_{i,j-1}\)，现试化简 \(\rm lcm(b,\frac{ab}{a-b})\)
\[\begin{aligned}&\rm lcm(b,\frac{ab}{a-b})\\ &\rm =\frac{ab^2}{(a-b)gcd(b,\frac{ab}{a-b})}\\ &\rm =\frac{ab^2}{gcd(ab-b^2,ab)}\\ &\rm =\frac{ab^2}{bgcd(a-b,b)}\\ &\rm=\frac{ab}{gcd(a,b)}\\ &\rm=lcm(a,b) \end{aligned}\]同理可得每个询问本质上是在问 \(\rm lcm_{j=n-k+1}^n j\)，使用主席树维护每个 \(n\) 的答案，rt[n] 下的后 \(k\) 个叶子的乘积对应询问 \(k\)，考察 \(n\leftarrow n+1\) 发现是对 \(n\) 处放一个 \(n\)，对于每个\(p,c\) 满足 \(p^c|n,p^c\neq n\) 在 \(n-p^c\) 处乘 \(\frac 1p\)
Code Display
const int N=1e5+10,M=N*200;
int rt[N],ls[M],rs[M],mult[M],Q,n,k;
int pri[N],tot,Time,cnt;
bool fl[N];
inline void upd(int &p,int pre,int l,int r,int pos,int dlt){
if(p<=Time) p=++tot,mult[p]=pre?mult[pre]:1,ls[p]=ls[pre],rs[p]=rs[pre]; ckmul(mult[p],dlt);
if(l==r) return ; int mid=(l+r)>>1;
if(pos<=mid) upd(ls[p],ls[pre],l,mid,pos,dlt);
else upd(rs[p],rs[pre],mid+1,r,pos,dlt);
return ;
}
inline int Query(int p,int l,int r,int st,int ed){
if(!p) return 1; if(st<=l&&r<=ed) return mult[p];
int mid=(l+r)>>1;
if(ed<=mid) return Query(ls[p],l,mid,st,ed);
if(st>mid) return Query(rs[p],mid+1,r,st,ed);
return mul(Query(ls[p],l,mid,st,ed),Query(rs[p],mid+1,r,st,ed));
}
int C[N],D[N],inv[N];
signed main(){
n=N-10;
for(int i=2;i<=n;++i){
if(!fl[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i<=n;++j){
fl[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
inv[0]=inv[1]=1;
for(int i=2;i<=n;++i){
int x=i; Time=tot; rt[i]=rt[i-1];
inv[i]=mod-mul(mod/i,inv[mod%i]);
upd(rt[i],rt[i],1,1e5,i,i);
for(int j=1;pri[j]*pri[j]<=x;++j) if(x%pri[j]==0){
int val=1;
while(x%pri[j]==0){
val*=pri[j];
x/=pri[j];
if(i^val) upd(rt[i],rt[i],1,1e5,i-val,inv[pri[j]]);
}
}
if(x!=i&&x>1) upd(rt[i],rt[i],1,1e5,i-x,inv[x]);
}
int Q=read(); n=read(); k=read();
int lans=Query(rt[n],1,1e5,n-k+1,n),A=read(),B=read(),Mod=read();
for(int i=2;i<=Q;++i) C[i]=read();
print(lans);
rep(i,2,Q){
D[i]=read();
n=(A*lans+C[i])%Mod+1;
k=(B*lans+D[i])%n+1;
print(lans=Query(rt[n],1,1e5,n-k+1,n));
}
return 0;
}
点点的最大流
最大流是最小割，回到仙人掌上面就是树边或者环上入点到出点的两条路径的最小边权之和
使用树链剖分维护仙人掌缩点之后得到的广义圆方树，同时对每个环维护一套 \(\rm RMQ\)，这里可以不对两个点对应的点双建立虚点来减少细节
在重链剖分初始化时，将虚点和父亲是虚点的链顶的权置为无穷大，将树边儿子权值置为边权，虚点重儿子权值置为该点走出点双的两段路径最小值之和
查询过程中重链可以直接跳，轻链跳出链顶时处理链顶父亲是虚点的情况，这里最小值需要在 \(\rm RMQ\) 中得到
如果 \(\rm LCA\) 是虚点需要最后再在环里面做 \(\rm RMQ\)，可以写一个支持单点修改、查询区间最小值的线段树来做
对修改操作，树边直接修改儿子权值即可，环边需要修改 \(\rm RMQ\) 并更新重儿子权值以保证跳重链的正确性
个人认为这题就是揉的板子多些，甚至都不一定吓人，真正稍有价值的 case 都可以通过将点权设为正无穷来规避掉，同时如果实现一个可以简洁调用的 \(\rm RMQ\) 那么这题目实现也挺平凡的
Code Display
const int N=4e5+10,inf=0x3f3f3f3f3f;
int n,m,Q,a[N],nds,bel[N],id[N];
struct Seg{
vector Mn;
int Rbound,Lbound;
inline void init(int lll,int rrr){Lbound=lll; Rbound=rrr; Mn.resize(rrr<<2|1); return ;}
#define ls p<<1
#define rs p<<1|1
inline void push_up(int p){Mn[p]=min(Mn[ls],Mn[rs]); return ;}
inline void Modify(int pos,int v,int p=1,int l=-1,int r=-1){
if(p==1) l=Lbound,r=Rbound;
if(l==r) return Mn[p]=v,void(); int mid=(l+r)>>1;
if(pos<=mid) Modify(pos,v,ls,l,mid); else Modify(pos,v,rs,mid+1,r);
return push_up(p);
}
inline int Query(int st,int ed,int p=1,int l=-1,int r=-1){
if(ed>1;
if(ed<=mid) return Query(st,ed,ls,l,mid);
if(st>mid) return Query(st,ed,rs,mid+1,r);
return min(Query(st,ed,ls,l,mid),Query(st,ed,rs,mid+1,r));
}
inline void build(int p=1,int l=-1,int r=-1){
if(p==1) l=Lbound,r=Rbound;
if(l==r) return Mn[p]=a[l],void(); int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
return push_up(p);
}
#undef ls
#undef rs
}All,Ring[N];
inline int Ring_Query(int id,int st,int ed=1){
assert(st^ed); if(st>ed) swap(st,ed);
int siz=Ring[id].Rbound;
assert(st<=siz);
return Ring[id].Query(st,ed-1)+min(Ring[id].Query(ed,siz),Ring[id].Query(1,st-1));
}
struct Tree{
vector >g[N];
int dep[N],fa[N],top[N],dfn[N],ord[N],son[N],tim,siz[N];
inline void ins(int x,int y,int z){
g[x].pb({y,z}); g[y].pb({x,z});
return ;
}
inline void dfs1(int x,int fat){
dep[x]=dep[fa[x]=fat]+(siz[x]=1);
for(auto e:g[x]) if(e.fir^fat){
dfs1(e.fir,x); siz[x]+=siz[e.fir];
if(siz[son[x]]n) a[dfn[i]]=inf;
else if(fa[i]>n&&son[fa[i]]!=i) a[dfn[i]]=inf;
else a[dfn[i]]=Ring_Query(bel[i],id[i]);
}
All.build(); return ;
}
inline void Modify(int x,int y,int z){
if(bel[x]&&bel[x]==bel[y]){
int siz=Ring[bel[x]].Rbound;
if(id[x]>id[y]) swap(x,y);
if(id[x]==1&&id[y]==siz) Ring[bel[x]].Modify(siz,z);
else Ring[bel[x]].Modify(id[x],z);
int hs=son[bel[x]];
All.Modify(dfn[hs],Ring_Query(bel[x],id[hs]));
}else{
if(dep[x]n){
ckmin(res,Ring_Query(fa[top[x]],id[top[x]]));
x=fa[fa[top[x]]];
}else x=fa[top[x]];
}
ckmin(res,All.Query(dfn[Top]+1,dfn[x]));
return res;
}
inline int Query(int x,int y){
int lca=get_Lca(x,y);
int res=inf,sx=get_son(lca,x),sy=get_son(lca,y);
if(lca>n) return min(Ring_Query(lca,id[sx],id[sy]),min(ask_chain(x,sx),ask_chain(y,sy)));
return min(ask_chain(x,lca),ask_chain(y,lca));
}
}T;
map ,int> edge;
inline void ins(int x,int y,int z){if(x>y) swap(x,y); edge[{x,y}]=z;}
inline int ask(int x,int y){if(x>y) swap(x,y); return edge[{x,y}];}
int dfn[N],low[N],stk[N],top,tim;
vector G[N];
inline void tarjan(int x){
dfn[x]=low[x]=++tim; stk[++top]=x;
for(auto t:G[x]){
if(!dfn[t]){
tarjan(t); ckmin(low[x],low[t]);
if(low[t]==dfn[x]){
vector ar={x};
do ar.push_back(stk[top]); while(stk[top--]!=t);
if(ar.size()==2){
T.ins(x,t,ask(x,t));
continue;
}else{
++nds;
for(auto node:ar){
bel[node]=nds;
T.ins(node,nds,0);
}
int siz=ar.size();
Ring[nds].init(1,siz);
for(int i=1;i<=siz;++i) id[ar[i-1]]=i,a[i]=ask(ar[i-1],ar[i%siz]);
Ring[nds].build();
}
}
}else ckmin(low[x],dfn[t]);
} return ;
}
int u[N],v[N],w[N];
signed main(){
nds=n=read(); m=read();
for(int i=1;i<=m;++i){
u[i]=read(),v[i]=read(),w[i]=read();
G[u[i]].push_back(v[i]),G[v[i]].push_back(u[i]);
ins(u[i],v[i],w[i]);
}
tarjan(1);
T.init();
int Q=read(); while(Q--){
if(read()){
int eid=read(),val=read();
T.Modify(u[eid],v[eid],val);
}else print(T.Query(read(),read()));
}
return 0;
}