省选前复习
网络流
1.最大流/最小割
先 bfs 对图分层，这里只走有流量的边。
然后从源点出发 dfs，每次只往层数为 \(d_u+1\) 的点流，这样每次都是最短的路径。
当前弧优化就是把 head 指针移动到这个位置。
还有如果一个点满流就要删掉。
P3376
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int N=205,M=5005;
const ll inf=1e18;
int n,m,s,t,head[N],edgenum=1,dep[N],cur[N];
struct edge{
int to,nxt,val;
}e[M*2];
void add_edge(int u,int v,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
head[u]=edgenum;
}
queue<int> q;
bool bfs()
{
for(int i=1;i<=n;i++) cur[i]=head[i],dep[i]=1e9;
q.push(s),dep[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val&&dep[v]>n)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[t]<=n) return 1;
return 0;
}
ll dfs(int u,ll flow)
{
// printf("%d %lld\n",u,flow);
if(u==t||flow==0) return flow;
ll res=flow;
for(int i=cur[u];i;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].to,w=e[i].val;
if(w&&dep[v]==dep[u]+1)
{
ll k=dfs(v,min(1ll*w,res));
res-=k,e[i].val-=k,e[i^1].val+=k;
}
}
if(res==flow) dep[u]=0;
return flow-res;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w),add_edge(v,u,0);
}
ll ans=0;
while(bfs())
{
ans+=dfs(s,inf);
}
printf("%lld",ans);
return 0;
}
2.费用流
先 spfa 找费用最短路，然后把这条路流满，重复这个过程。
P3381
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int M=5e4+5,N=5005;
const ll inf=1e17;
int n,m,s,t,head[N],edgenum=1;
struct edge{
int nxt,to,flow,val;
}e[M*2];
void add_edge(int u,int v,int f,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
e[edgenum].flow=f;
head[u]=edgenum;
}
int flow[N],pre[N];
ll dis[N],maxf,minc;
bool inq[N];
queue<int> q;
bool spfa()
{
for(int i=1;i<=n;i++) flow[i]=0,dis[i]=inf;
q.push(s),inq[s]=1,dis[s]=0,flow[s]=1e9;
while(!q.empty())
{
int u=q.front();
inq[u]=0;
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to,f=e[i].flow,w=e[i].val;
if(f&&dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w,flow[v]=min(flow[u],f);
pre[v]=i;
if(!inq[v]) inq[v]=1,q.push(v);
}
}
}
if(dis[t]<inf) return 1;
return 0;
}
void MCMF()
{
maxf+=flow[t],minc+=flow[t]*dis[t];
int x=t;
while(x!=s)
{
e[pre[x]^1].flow+=flow[t],e[pre[x]].flow-=flow[t];
x=e[pre[x]^1].to;
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int u,v,w,c;
scanf("%d%d%d%d",&u,&v,&w,&c);
add_edge(u,v,w,c),add_edge(v,u,0,-c);
}
while(spfa())
{
// printf("a");
MCMF();
}
printf("%lld %lld",maxf,minc);
return 0;
}
3.上下界网络流
先流满下界，然后考虑让流守恒。先建出上界和下界差的图，就是还能流的量，源点向流入较多的点连边，流出较多到汇点。
跑最大流，满流就可行，最大流就是残量网络最大流，最小流就是建反图的最大流。
P14578
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int M=2e4+5,N=1e3+5;
int n,m,head[N],edgenum=1,d[N],cur[N],dep[N],mn[M*2];
struct edge{
int to,nxt,val;
}e[M*2];
void add_edge(int u,int v,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
head[u]=edgenum;
}
queue<int> q;
bool bfs()
{
for(int i=1;i<=n+2;i++) cur[i]=head[i],dep[i]=1e9;
q.push(n+2),dep[n+2]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].val&&dep[v]>1e6)
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
if(dep[n+1]<1e9) return 1;
return 0;
}
int dfs(int u,int flow)
{
if(u==n+1||flow==0) return flow;
int res=flow;
for(int i=cur[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].val;
cur[u]=i;
if(w&&dep[v]==dep[u]+1)
{
int k=dfs(v,min(res,w));
res-=k,e[i].val-=k,e[i^1].val+=k;
}
}
if(res==0) dep[u]=0;
return flow-res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,l,r;
scanf("%d%d%d%d",&u,&v,&l,&r);
d[u]-=l,d[v]+=l,mn[edgenum+1]=l;
add_edge(u,v,r-l),add_edge(v,u,0);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(d[i]>0)
{
add_edge(n+2,i,d[i]),add_edge(i,n+2,0);
ans+=d[i];
}
else add_edge(i,n+1,-d[i]),add_edge(n+1,i,0);
}
while(bfs())
{
ans-=dfs(n+2,1e9);
}
if(ans==0)
{
printf("Yes\n");
for(int i=1;i<=m;i++)
{
printf("%d\n",mn[i*2]+e[i*2+1].val);
}
}
else printf("No");
return 0;
}
后缀数组
相当于求后缀的字典序排序，类似倍增去做，每次只选前 \(2^i\) 个位置进行排序。
此时如果已知一个层次的排序结果，推到下一个层次就是将 \(x\) 和 \(x+2^i\) 的次序拼起来，然后用这个新数排序，可以基数排序实现。
P3809
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
const int N=1e6+6;
int n,ch[150],a[N*2],p1[N],p2[N],b[N],cnt[N],c[N];
string s;
void solve()
{
for(int i=1;i<=n;i++) cnt[p2[i]]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) c[cnt[p2[i]]]=i,cnt[p2[i]]--;
for(int i=1;i<=n;i++) b[i]=c[i],cnt[i]=0;
for(int i=1;i<=n;i++) cnt[p1[i]]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--) c[cnt[p1[b[i]]]]=b[i],cnt[p1[b[i]]]--;
for(int i=1;i<=n;i++) b[i]=c[i],cnt[i]=0;
int tot=1;
a[b[1]]=1;
for(int i=2;i<=n;i++)
{
if(p1[b[i]]==p1[b[i-1]]&&p2[b[i]]==p2[b[i-1]]) a[b[i]]=tot;
else a[b[i]]=++tot;
}
}
int main()
{
cin>>s;
n=s.size(),s=" "+s;
for(int i=1;i<=n;i++) ch[(int)s[i]]=1;
for(int i=1;i<=130;i++) ch[i]+=ch[i-1];
for(int i=1;i<=n;i++) a[i]=ch[(int)s[i]];
for(int i=0;;i++)
{
if((1<<i)>=n) break;
for(int j=1;j<=n;j++) p1[j]=a[j],p2[j]=a[j+(1<<i)],b[j]=j;
// for(int j=1;j<=n;j++) printf("%d %d\n",p1[j],p2[j]);
// printf("\n");
solve();
}
for(int i=1;i<=n;i++) b[a[i]]=i;
for(int i=1;i<=n;i++)
{
printf("%d ",b[i]);
}
return 0;
}
记 \(rk_i\) 为 \(i\) 开头后缀的排名，\(sa_i\) 为排名为 \(i\) 后缀的开头。
\(height_i=lcp(sa_i,sa_{i-1})\)
有 \(height_{rk_i}\ge height_{rk_{i-1}}+1\)
因为开头在 \(i-1\) 位置的串和恰好比它字典序小 1 的串去掉开头就是 \(i\) 的一组贡献。
经典问题：求几个串的公共子串/求两个串的公共前缀长度（多次询问）。
排序后两个串的 lcp 就是在排名上两点之间所有 height 的 min。
SAM
woc，人生第一次看懂！
首先正常的边是起点是终点的前缀，后缀链接是后缀。
构建上，加入一个新的字符，把 \(lst\) 到后缀链接根上所有后面没有这个字符的连到当前点。
然后找到第一个有值的位置 \(q\)，如果 \(len=len_p+1\) 那么必然是跳到的点直接连出来的，此时它的 endpos 集合就多了一个当前点 \(now\)，并且 \(q\) 一定是 \(now\) 的后缀，\(now\) 的 endpos 集合包含于 \(q\)。
否则，相当于 \(q\) 的一个后缀是与 \(now\) 相同的，而因为前面不同，\(now\) 和 \(q\) 的 endpos 集合是不交的，并且恰好应该在这个位置合并。
所以应该建立一个新的节点表示这里的公共后缀和 endpos 集合。
P3804
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
const int N=1e6+5;
int n,tot,lst,cnt[N*2],b[N*2],siz[N*2],vis[N*2];
struct node{
int ch[26],link,len;
}tr[N*2];
void insert(int x)
{
int now=++tot,p=lst;
tr[now].len=tr[p].len+1;
siz[now]=1;
while(p!=-1&&!tr[p].ch[x])
{
tr[p].ch[x]=now;
p=tr[p].link;
}
if(p==-1) tr[now].link=0;
else
{
int q=tr[p].ch[x];
if(tr[q].len==tr[p].len+1)
{
tr[now].link=q;
}
else
{
tot++;
tr[tot]=tr[q],tr[tot].len=tr[p].len+1;
while(p!=-1&&tr[p].ch[x]==q)
{
tr[p].ch[x]=tot;
p=tr[p].link;
}
tr[now].link=tr[q].link=tot;
}
}
lst=now;
}
string s;
int main()
{
cin>>s;
n=s.size();
tr[0].link=-1;
for(int i=0;i<n;i++) insert(s[i]-'a');
for(int i=1;i<=tot;i++)
{
cnt[tr[i].len]++;
}
for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;i++) b[cnt[tr[i].len]]=i,cnt[tr[i].len]--;
long long ans=0;
for(int i=tot;i>0;i--)
{
int x=b[i];
if(siz[x]>1)
ans=max(ans,1ll*tr[x].len*siz[x]);
siz[tr[x].link]+=siz[x];
}
printf("%lld",ans);
return 0;
}
应用上有一堆：
1.求不同子串个数，两种方法，一种是从根 dfs 求路径数，一种是因为每个节点的 endpos 集合不同，所以包含的串集合一定不同，就是 \(\sum len(x)-len(link[x])\)
2.求公共子串，先对一个建立 SAM，然后发现 \(link\) 类似于 \(fail\)，每个串跑匹配，记录每个串在每个点最大值的最小值，全自动机取 \(max\)
3.求一个串的出现次数，预处理 endpos，匹配到位置的 \(endpos\) 大小就是答案。
4.endpos 相关可以主席树维护。
CDQ 分治
处理三维偏序问题，时间轴相关可以以时间为下标，然后离线。
具体实现上一维排序，一维分治，每次计算跨过分治位置的贡献，套个树状数组，时间复杂度 \(O(n\log^2 n)\)
P3810
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,k,a[N],b[N],c[N],id[N],d[N],f[N],sum[N],t[N];
bool fl[N];
bool cmp(int x,int y)
{
if(a[x]!=a[y]) return a[x]<a[y];
if(b[x]!=b[y]) return b[x]<b[y];
return c[x]<c[y];
}
bool cmp1(int x,int y)
{
if(b[x]!=b[y]) return b[x]<b[y];
if(a[x]!=a[y]) return a[x]<a[y];
return c[x]<c[y];
}
struct BIT{
int sum[N];
void add(int x,int v)
{
while(x<=k)
{
sum[x]+=v;
x+=(x&(-x));
}
}
int query(int x)
{
int res=0;
while(x)
{
res+=sum[x];
x-=(x&(-x));
}
return res;
}
}T;
void cdq(int n,int *p)
{
if(n==1) return;
int m1=n/2,m2=n-m1;
int p1[m1+1],p2[m2+1];
for(int i=1;i<=n;i++) d[i]=p[i];
sort(p+1,p+n+1,cmp1);
for(int i=1;i<=m1;i++) fl[p[i]]=1;
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++)
{
if(fl[d[i]]) p1[++cnt1]=d[i];
else p2[++cnt2]=d[i];
}
cnt1=1;
for(int i=1;i<=m1;i++) fl[p[i]]=0;
// printf("%d %d\n",m1,m2);
for(int i=1;i<=m2;i++)
{
// printf("%d %d\n",i,cnt2);
while(cnt1<=m1&&a[p1[cnt1]]<=a[p2[i]])
{
T.add(c[p1[cnt1]],sum[p1[cnt1]]);
cnt1++;
}
f[p2[i]]+=T.query(c[p2[i]]);
// printf("%d ",f[p2[i]]);
}
for(int i=1;i<cnt1;i++)
{
T.add(c[p1[i]],-sum[p1[i]]);
}
cdq(m1,p1),cdq(m2,p2);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
id[i]=i;
}
sort(id+1,id+n+1,cmp);
// printf("\n");
// for(int i=1;i<=n;i++)
// {
// printf("%d %d %d\n",a[id[i]],b[id[i]],c[id[i]]);
// }
int tmp=1;
sum[id[1]]=1;
for(int i=2;i<=n;i++)
{
if(a[id[i]]==a[id[tmp]]&&b[id[i]]==b[id[tmp]]&&c[id[i]]==c[id[tmp]])
{
sum[id[tmp]]++;
}
else id[++tmp]=id[i],sum[id[tmp]]=1;
}
cdq(tmp,id);
// for(int i=1;i<=tmp;i++) printf("%d ",sum[id[i]]);
for(int i=1;i<=tmp;i++)
{
t[f[id[i]]+sum[id[i]]-1]+=sum[id[i]];
// printf("%d %d %d\n",id[i],f[id[i]],sum[id[i]]);
}
for(int i=0;i<n;i++)
{
printf("%d\n",t[i]);
}
return 0;
}
点分治&点分树
应用比较像，就写一块了。
点分治就是每次找重心，找跨过重心的贡献，时间复杂度 \(O(n\log n)\)，但是因为常数比较大，询问比较少的时候一定要离线。
P3806
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e4+5,M=1e7+5;
int n,m,k[N],head[N],edgenum,vis[N],siz[N],mx[N];
int dep[N],p[N],cnt,ans[N];
bool fl[M];
struct edge{
int to,nxt,val;
}e[N*2];
void add_edge(int u,int v,int w)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
head[u]=edgenum;
}
inline int dfs1(int u,int fa,int s)
{
siz[u]=1,mx[u]=0;
int p=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
int x=dfs1(v,u,s);
mx[u]=max(mx[u],siz[v]),siz[u]+=siz[v];
if(mx[p]>mx[x]) p=x;
}
mx[u]=max(mx[u],s-siz[u]);
if(mx[u]<mx[p]) p=u;
return p;
}
inline void dfs2(int u,int fa)
{
p[++cnt]=u;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa||vis[v]) continue;
dep[v]=dep[u]+e[i].val;
dfs2(v,u);
}
}
inline void dfs(int u,int fa)
{
u=dfs1(u,fa,siz[u]);
// printf("%d ",u);
vis[u]=1;
cnt=0;
fl[0]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
int tmp=cnt;
// printf("%d ",v);
dep[v]=e[i].val;
dfs2(v,u);
for(int j=tmp+1;j<=cnt;j++)
{
for(int t=1;t<=m;t++)
{
if(dep[p[j]]<=k[t])
{
if(fl[k[t]-dep[p[j]]]) ans[t]=1;
}
}
}
for(int j=tmp+1;j<=cnt;j++)
{
if(dep[p[j]]<=1e7) fl[dep[p[j]]]=1;
}
}
fl[0]=0;
for(int j=1;j<=cnt;j++)
{
if(dep[p[j]]<=1e7) fl[dep[p[j]]]=0;
}
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
dfs(v,u);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
mx[0]=1e9;
for(int i=1;i<=m;i++)
{
scanf("%d",&k[i]);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
if(ans[i]) printf("AYE\n");
else printf("NAY\n");
}
return 0;
}
点分树就是每次把重心找出来，然后按层次连边，这样就是一个深度只有 log 层的树。
每个节点的信息和点分治类似，就是删除它的时候所在连通块的贡献。
修改就暴力跳父亲，查询可能麻烦一点，因为点分治是查跨过这个点的贡献，要把在同一个子树内的贡献容斥掉，其实把系数挂在儿子就是一种方法。
P6329
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5,M=1e7+5;
int n,m,a[N],head[N],edgenum,dep[N],f[N][20],d[N];
int siz[N],mx[N],f1[N],p[N],cnt,f2[N],dis[N][21];
bool vis[N];
struct edge{
int nxt,to;
}e[N*2];
void add_edge(int u,int v)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1,f[u][0]=fa;
for(int i=1;i<20;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
if(x==y) return x;
}
for(int i=19;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int getdis(int x,int y)
{
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int rt1[N],rt2[N],l1[N],l2[N],ls[M],rs[M],sum[M],tot;
int update(int id,int l,int r,int x,int val)
{
if(!id) id=++tot;
if(l==r)
{
sum[id]+=val;
return id;
}
int mid=(l+r)>>1;
if(x<=mid) ls[id]=update(ls[id],l,mid,x,val);
else rs[id]=update(rs[id],mid+1,r,x,val);
sum[id]=sum[ls[id]]+sum[rs[id]];
return id;
}
int query(int id,int l,int r,int ql,int qr)
{
if(!id||l>r) return 0;
if(ql==l&&qr==r)
{
return sum[id];
}
int mid=(l+r)>>1;
if(qr<=mid) return query(ls[id],l,mid,ql,qr);
else if(ql>mid) return query(rs[id],mid+1,r,ql,qr);
else return query(ls[id],l,mid,ql,mid)+query(rs[id],mid+1,r,mid+1,qr);
}
int dfs2(int u,int fa,int s)
{
siz[u]=1,mx[u]=0;
int p=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa||vis[v]) continue;
int x=dfs2(v,u,s);
siz[u]+=siz[v],mx[u]=max(mx[u],siz[v]);
if(mx[p]>mx[x]) p=x;
}
mx[u]=max(mx[u],s-siz[u]);
if(mx[u]<mx[p]) p=u;
return p;
}
void dfs3(int u,int fa)
{
p[++cnt]=u,f2[u]=fa,siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa||vis[v]) continue;
siz[u]+=siz[v];
dfs3(v,u);
}
}
void dfs1(int u,int fa)
{
u=dfs2(u,fa,siz[u]);
f1[u]=fa,cnt=0;
dfs3(u,0);
for(int i=1;i<=cnt;i++) l1[u]=max(l1[u],d[p[i]]);
for(int i=1;i<=cnt;i++)
{
int x=p[i];
if(fa!=0) rt1[u]=update(rt1[u],1,l1[u],d[x],a[x]);
d[x]=d[f2[x]]+1,l2[u]=max(l2[u],d[x]);
}
for(int i=1;i<=cnt;i++)
{
int x=p[i];
rt2[u]=update(rt2[u],1,l2[u],d[x],a[x]);
// if(u==13)
// printf("d%d %d ",x,query(rt2[u],1,l2[u],1,2));
}
// printf("\n");
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
dfs1(v,u);
}
}
void solve(int x)
{
int cnt=0,y=f1[x];
dis[x][0]=1;
while(y)
{
dis[x][++cnt]=getdis(x,y)+1;
y=f1[y];
}
}
void change(int x,int y)
{
int t=x,cnt=0;
// printf("%d\n",x);
rt2[x]=update(rt2[x],1,l2[x],1,y-a[x]);
while(f1[t])
{
cnt++;
// printf("%d ",dis[x][cnt]);
rt1[t]=update(rt1[t],1,l1[t],dis[x][cnt],y-a[x]);
t=f1[t];
rt2[t]=update(rt2[t],1,l2[t],dis[x][cnt],y-a[x]);
}
a[x]=y;
}
int getans(int x,int y)
{
int t=x,cnt=0,ans=query(rt2[x],1,l2[x],1,min(y+1,l2[x]));
// printf("%d ",ans);
while(f1[t])
{
cnt++;
ans-=query(rt1[t],1,l1[t],1,min(y+2-dis[x][cnt],l1[t]));
t=f1[t];
ans+=query(rt2[t],1,l2[t],1,min(y+2-dis[x][cnt],l2[t]));
// printf("%d %d %d a%d\n",t,l2[t],ans,min(y+2-dis[x][cnt],l2[t]));
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(1,0);
// printf("a");
mx[0]=1e9,siz[1]=n;
dfs1(1,0);
for(int i=1;i<=n;i++)
{
// printf("p%d ",f1[i]);
solve(i);
}
int ans=0;
while(m--)
{
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
x^=ans,y^=ans;
if(opt==1) change(x,y);
else
{
ans=getans(x,y);
printf("%d\n",ans);
}
}
return 0;
}
虚树
难点在于建树。
考虑哪些点会在虚树上，分别是关键点和原来的点的 lca。
考虑遍历的过程，相当于一个栈，里面存当前链，建立虚树的过程是相似的。
先按 dfs 序排序，开一个栈维护，每次判断是不是栈顶点的儿子，如果不是找到 lca，以此类推，直到可以放入 lca。
P2495
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2.5e5+5;
int n,m,head[N],edgenum,dep[N],f[N][20],d[N][20],dfn[N],idx;
int b[N],st[N],cnt,id[N],siz[N],top;
bool fl[N];
struct edge{
int to,nxt,val;
}e[N*2];
void add_edge(int u,int v,int w)
{
// printf("%d %d %d\n",u,v,w);
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
e[edgenum].val=w;
head[u]=edgenum;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1,f[u][0]=fa;
dfn[u]=++idx,siz[u]=1;
for(int i=1;i<20;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
d[u][i]=min(d[u][i-1],d[f[u][i-1]][i-1]);
}
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
d[v][0]=e[i].val;
dfs(v,u);
siz[u]+=siz[v];
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
if(x==y) return x;
}
for(int i=19;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int getval(int x,int y)
{
int ans=1e9;
for(int i=19;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
ans=min(ans,d[x][i]);
x=f[x][i];
}
}
return ans;
}
void init()
{
for(int i=1;i<=cnt;i++)
{
int x=id[i];
head[x]=fl[x]=0;
}
edgenum=cnt=0;
}
bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
bool check(int x,int y)
{
if(x==y) return 1;
if(dfn[x]>dfn[y]&&dfn[x]<dfn[y]+siz[y]) return 1;
return 0;
}
ll dp[N];
void dfs1(int u)
{
ll sum=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
dp[v]=e[i].val;
dfs1(v);
sum+=dp[v];
}
if(!fl[u]) dp[u]=min(dp[u],sum);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(1,0);
for(int i=1;i<=n;i++) head[i]=0;
edgenum=0;
scanf("%d",&m);
while(m--)
{
init();
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&b[i]);
fl[b[i]]=1;
}
sort(b+1,b+k+1,cmp);
top=1,st[top]=1,id[++cnt]=1;
for(int i=1;i<=k;i++)
{
int x=b[i],now;
id[++cnt]=b[i];
if(check(x,st[top]))
{
st[++top]=x;
continue;
}
int lc=lca(x,st[top]);
// printf("%d %d\n",x,lc);
now=st[top],top--;
while(!check(lc,st[top]))
{
add_edge(st[top],now,getval(now,st[top]));
now=st[top],top--;
}
if(st[top]!=lc)
{
id[++cnt]=lc,st[++top]=lc;
}
st[++top]=x,add_edge(lc,now,getval(now,lc));
}
for(int i=1;i<top;i++) add_edge(st[i],st[i+1],getval(st[i+1],st[i]));
dp[1]=1e17;
dfs1(1);
printf("%lld\n",dp[1]);
}
return 0;
}
AC 自动机
算了，记录每个点到的次数，fail 树上求子树和。
代码说明一切。
P5357
#include<cstdio>
#include<string>
#include<queue>
#include<iostream>
using namespace std;
const int N=2e5+5;
int n,ed[N],fail[N],cnt[N],head[N],edgenum,tot;
struct trie{
int ch[26];
}tr[N];
struct edge{
int nxt,to;
}e[N];
void add_edge(int u,int v)
{
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
int insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int v=s[i]-'a';
if(!tr[p].ch[v]) tr[p].ch[v]=++tot;
p=tr[p].ch[v];
}
return p;
}
queue<int> q;
void bfs()
{
for(int i=0;i<26;i++)
{
if(tr[0].ch[i]) q.push(tr[0].ch[i]);
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<26;i++)
{
if(tr[u].ch[i])
{
fail[tr[u].ch[i]]=tr[fail[u]].ch[i];
q.push(tr[u].ch[i]);
}
else
{
tr[u].ch[i]=tr[fail[u]].ch[i];
}
}
}
}
void solve(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int v=s[i]-'a';
while(p&&!tr[p].ch[v]) p=fail[p];
p=tr[p].ch[v];
cnt[p]++;
}
}
void dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
dfs(v);
cnt[u]+=cnt[v];
}
}
int main()
{
// freopen("1.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
ed[i]=insert(s);
}
bfs();
string s;
cin>>s;
solve(s);
for(int i=1;i<=tot;i++) add_edge(fail[i],i);
dfs(0);
for(int i=1;i<=n;i++)
{
printf("%d\n",cnt[ed[i]]);
}
return 0;
}
Pollard_Rho
令 \(f(x)=x^2+c\)，那么这个至多 \(\sqrt p\) 次就会成环，所以可以考虑记录差值，然后如果是 \(n\) 的因数就可以结束。
考虑倍增跳环，没成环就把 \(s\) 移动到 \(t\)，因为 \(gcd(ab,n)=gcd(ab\bmod n,n)\)，所以可以每大约 128 个数判断一次，乘积 \(=0\) 说明成环。
还有质数判断，因为范围很大，考虑 miller_rabin。
这个是基于二次探测定理，就是 \(x^2\equiv 1(\bmod p)\)，\(p\) 为质数的解只有 \(1\),\(p-1\)。
由费马小定理，\(a^{p-1}\equiv 1(\bmod p)\)，记 \(p=u2^t\) 直接判断 \(a^{u},a^{2u},\dots\) 的结果有没有 \(1\) 或 \(p-1\)
但是因为不完全正确，所以要多随机几个。
P4718
#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937_64 rnd(time(0));
int T,p[15]={0,2,3,5,7,11,13,17,19,23,29,31,37};
ll n,mx;
ll mul(ll x,ll y,ll p)
{
return (__int128)x*y%p;
}
ll qpow(ll x,ll y,ll p)
{
ll res=1;
while(y)
{
if(y&1) res=mul(res,x,p);
x=mul(x,x,p);
y>>=1;
}
return res;
}
bool miller_rabin(ll x)
{
if(x==2||x==3) return 1;
if(x%2==0||x%3==0||x==1) return 0;
ll u=x-1,t=0;
while(u%2==0) u/=2,t++;
for(int i=1;i<=12;i++)
{
if(p[i]>=x) break;
ll a=p[i],v=qpow(a,u,x),s;
// printf("%d %lld %lld %lld\n",a,x,u,v);
if(v==1) continue;
for(s=0;s<t;s++)
{
if(v==x-1) break;
v=mul(v,v,x);
}
if(s==t) return 0;
}
return 1;
}
ll gcd(ll a,ll b)
{
if(b==0) return a;
return gcd(b,a%b);
}
ll pollard_rho(ll x)
{
if(x==4) return 2;
ll c=1ll*rnd()%x,s=0,t=0;
for(int i=1;;i<<=1,s=t)
{
// i=min(i,512);
ll val=1;
for(int j=1;j<=i;j++)
{
t=(mul(t,t,x)+c)%x;
val=mul(val,s>t?s-t:t-s,x);
if(!val) return x;
if(j%128==0)
{
ll d=gcd(val,x);
if(d!=1) return d;
}
}
ll d=gcd(val,x);
if(d!=1) return d;
}
}
inline void solve(ll x)
{
if(x<2||x<mx) return;
if(miller_rabin(x))
{
mx=max(mx,x);
return;
}
// printf("%lld ",x);
ll p=pollard_rho(x);
solve(p),solve(x/p);
}
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
mx=0;
solve(n);
if(mx==n) printf("Prime\n");
else printf("%lld\n",mx);
}
return 0;
}
浙公网安备 33010602011771号