DECO*27 - 乙女解剖 feat. 初音未来
很难很难的数据结构。T-T
[LNOI2014] LCA
题意
给定一棵 \(n\) 个点的有根树，\(m\) 次询问，每次询问给定 \(l,r,z\)，求 \(\sum\limits_{i=l}^{r}dep_{\operatorname{lca}(i,z)}\)。
\(1\le n,m\le 5\times 10^4\)。
solution
题单里最简单的题。
首先令 \(f(r,z)=\sum\limits_{i=1}^{r}dep_{\operatorname{lca}(i,z)}\)，那么每个询问的答案就是 \(f(r,z)-f(l-1,z)\)，考虑使用扫描线求出 \(f(r,z)\)。
两个点的 LCA 深度就是两个点到根的路径交集点数，对 \(r\) 扫描线，每次加入一个 \(r\) 相当于对于 \(r\) 到根节点的路径上所有点权值加 \(1\)，处理一个挂在 \(r\) 上的询问 \(f(r,z)\) 的答案就是 \(z\) 到根节点路径权值和。
树剖维护一下，时间复杂度 \(O((n+m)\log^2 n)\)。
Code
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=5e4+10;
constexpr int inf=1e9+10;inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,m,idx;
ll ans[N];
vector<int> e[N];int f[N],dep[N],siz[N],son[N];
int top[N],dfn[N];inline void dfs1(int now,int fa) {dep[now]=(f[now]=fa)+(siz[now]=1);for (int v:e[now]) {dfs1(v,now);siz[now]+=siz[v];if (siz[v]>siz[son[now]]) son[now]=v;}
}inline void dfs2(int now,int tp) {top[now]=tp;dfn[now]=++idx;if (!son[now]) return;dfs2(son[now],tp);for (int v:e[now]) if (v^son[now]) dfs2(v,v);
}struct Segment_Tree {ll s[N<<2],tg[N<<2];inline int ls(int x) {return x<<1;}inline int rs(int x) {return x<<1|1;}inline void modify(int x,int l,int r,int k) {s[x]+=1ll*(r-l+1)*k;tg[x]+=k;}inline void push_down(int x,int l,int r) {if (!tg[x]) return;int mid=l+r>>1,k=tg[x];tg[x]=0;modify(ls(x),l,mid,k);modify(rs(x),mid+1,r,k);}inline void update(int x,int y,int l,int r,int now) {if (x<=l&&y>=r) return modify(now,l,r,1);push_down(now,l,r);int mid=l+r>>1;if (x<=mid) update(x,y,l,mid,ls(now));if (y>mid) update(x,y,mid+1,r,rs(now));s[now]=s[ls(now)]+s[rs(now)];}inline ll query(int x,int y,int l,int r,int now) {if (x<=l&&y>=r) return s[now];push_down(now,l,r);int mid=l+r>>1;ll ret=0;if (x<=mid) ret=query(x,y,l,mid,ls(now));if (y>mid) ret+=query(x,y,mid+1,r,rs(now));return ret;}
}tr;inline void update(int x) {while (x) {tr.update(dfn[top[x]],dfn[x],1,n,1);x=f[top[x]];}
}inline ll query(int x) {ll ret=0;while (x) {ret+=tr.query(dfn[top[x]],dfn[x],1,n,1);x=f[top[x]];}return ret;
}struct ques{int x,id,op;};
vector<ques> vec[N];int main() {read(n);read(m);f(i,2,n) {int fa;read(fa);fa++;e[fa].push_back(i);}dfs1(1,0);dfs2(1,1);f(i,1,m) {int l,r,x;read(l);read(r);read(x);l++;r++;x++;vec[r].push_back({x,i,1});vec[l-1].push_back({x,i,-1});}f(i,1,n) {update(i);for (ques k:vec[i]) ans[k.id]+=query(k.x)*k.op;}f(i,1,m) printf("%lld\n",ans[i]%201314);return 0;
}
The Classic Problem
题意
给定一张 \(n\) 个节点 \(m\) 条边的无向图，一条边 \((u,v,x)\) 表示 \(u\) 到 \(v\) 存在一条边权为 \(2^x\) 的无向边，求 \(s\) 到 \(t\) 的最短路，输出最短路权值对 \(10^9+7\) 取模的结果并给出一条具体路径。
\(1\le n,m,x\le 10^5\)。
solution
显然要跑 Dijkstra，我们需要实现一个 __int100018，但是直接高精度显然是不行的，考虑使用数据结构表示一个数。
我们在 Dijkstra 中对于每个点的距离要实现的操作有：
- 对一个数加上 \(2^x\)；
- 比较两个数的大小。
发现可以使用可持久化线段树来维护一个数，维护 \(10^5+18\) 个二进制位下的数是 \(0\) 还是 \(1\)，考虑如何实现上面的两个操作。
- 加 \(2^x\)，找到最高的位置 \(p\) 满足 \([x,p]\) 位上面均为 \(1\)，那么加法进位就变成了 \([x,p]\) 均为 \(0\)，第 \(p\) 位上为 \(1\);
- 比较两个数的大小，可以找到最高的不相等位置，线段树二分即可，判断两个区间是否相同可以用哈希。
可持久化线段树支持区间覆盖，单点修改，找到最高不同位，于是做完了，梳理一下每个节点要维护哪些信息：左右儿子，权值模 \(10^9+7\) 意义下的值（这个值可以直接作为哈希值），哈希值（双模哈希是必要的），整个区间是否全部为 \(1\)，区间长度（维护哈希值要用）。
对于区间覆盖为 \(0\)，可以使用初始时 \(s\) 对应的树（全为 \(0\)）来覆盖子节点，直接将子节点指向这棵全为 \(0\) 的树，避免使用懒标记导致空间复杂度太高。
比较两个数和加法都是 \(O(\log x)\) 的，所以时间复杂度 \(O(m\log m\log x)\)，空间复杂度 \(O(m\log x)\)。
Code
#include<cstdio>
#include<algorithm>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
#define ll long long
#define qwq Ff472130
#define f(i,l,r) for (int i=l;i<=r;i++)
#define F(i,l,r) for (int i=l;i>=r;i--)
constexpr int N=1e5+110;
constexpr int V=1e5+100;
constexpr int P=(N<<8);
constexpr int inf=1e9+10;constexpr int mod=1e9+7;
inline int ad(int x,int y) {return ((x+y>=mod)?(x+y-mod):(x+y));}
inline void add(int &x,int y) {x=ad(x,y);}inline void read(int &x) {x=0;char ch=getchar();while (ch<48) ch=getchar(); while (ch>=48) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}int n,m,cnt;
int fr[N];struct Edge{int v,w;};
vector<Edge> e[N];int rt[N],pw1[N],pw2[N];
struct Segment_Tree {int tot;struct Node{int ls,rs,val,fl,len,H;}tr[P];#define ls(x) tr[x].ls#define rs(x) tr[x].rsinline void push_up(int x) {int l=ls(x),r=rs(x);tr[x].val=(1ll*tr[r].val*pw1[tr[l].len]+tr[l].val)%mod;tr[x].H=(1ll*tr[r].H*pw2[tr[l].len]+tr[l].H)%998244853;tr[x].fl=(tr[l].fl&tr[r].fl);}inline int build(int l,int r) {int now=++tot,mid=l+r>>1;tr[now].len=r-l+1;if (l==r) return now;tr[now].ls=build(l,mid);tr[now].rs=build(mid+1,r);return now;}inline int newNode(int x) {tr[++tot]=tr[x];return tot;}inline void assign(int x,int y,int l,int r,int &now,int p2) {now=newNode(now);if (x<=l&&y>=r) return now=p2,void();int mid=l+r>>1;if (x<=mid) assign(x,y,l,mid,ls(now),ls(p2));if (y>mid) assign(x,y,mid+1,r,rs(now),rs(p2));push_up(now);}inline void update(int x,int l,int r,int &now) {now=newNode(now);if (l==r) return tr[now].fl=tr[now].val=tr[now].H=1,void();int mid=l+r>>1;if (x<=mid) update(x,l,mid,ls(now));else update(x,mid+1,r,rs(now));push_up(now);}inline bool chk(int x,int y) {return (tr[x].val==tr[y].val)&&(tr[x].H==tr[y].H);}inline bool cmp(int x,int y,int l,int r) {if (l==r) return tr[x].val<tr[y].val;int mid=l+r>>1;if (!chk(rs(x),rs(y))) return cmp(rs(x),rs(y),mid+1,r);return cmp(ls(x),ls(y),l,mid);}inline int find_first(int x,int l,int r,int now) {if (tr[now].fl) return 0;if (l==r) return l;int mid=l+r>>1;if (x<=mid) {int ret=find_first(x,l,mid,ls(now));if (ret) return ret;}return find_first(x,mid+1,r,rs(now));}#undef ls#undef rs
}tr;struct int1e5 {int v;}dis[N];
inline bool operator ==(const int1e5 &x,const int1e5 &y) {return tr.chk(rt[x.v],rt[y.v]);}
inline bool operator <(const int1e5 &x,const int1e5 &y) {if (x==y) return 0;return tr.cmp(rt[x.v],rt[y.v],1,V);
}
inline bool operator >(const int1e5 &x,const int1e5 &y) {return (!x.v)||(!((x==y)||(x<y)));}
inline int1e5 operator +(const int1e5 &x,const int y) {int p=tr.find_first(y,1,V,rt[x.v]);rt[++cnt]=rt[x.v];if (p!=y) tr.assign(y,p-1,1,V,rt[cnt],1);tr.update(p,1,V,rt[cnt]);return {cnt};
}struct queue_Node {int id;int1e5 val;inline bool operator <(const queue_Node &x)const {return val>x.val;}
};inline int dij(int s,int t) {rt[++cnt]=dis[s].v=tr.build(1,V);priority_queue<queue_Node> q;q.push({s,dis[s]});bitset<N> vis;while (!q.empty()) {int now=q.top().id;q.pop();if (vis[now]) continue;vis.set(now);for (Edge E:e[now]) {int v=E.v,w=E.w;if (vis[v]) continue;int1e5 d=dis[now]+w;if (dis[v]>d) q.push({v,dis[v]=d}),fr[v]=now;}}if (!dis[t].v) return -1;return tr.tr[rt[dis[t].v]].val;
}int main() {read(n);read(m);pw1[0]=pw2[0]=1;f(i,1,V-1) {pw1[i]=ad(pw1[i-1],pw1[i-1]);pw2[i]=pw2[i-1]+pw2[i-1];pw2[i]-=(pw2[i]>=998244853?998244853:0);}f(i,1,m) {int u,v,w;read(u);read(v);read(w);w++;e[u].push_back({v,w});e[v].push_back({u,w});}int s,t;read(s);read(t);int ret=dij(s,t);printf("%d\n",ret);if (ret==-1) return 0;vector<int> path;while (t!=s) path.push_back(t),t=fr[t];path.push_back(s);reverse(path.begin(),path.end());printf("%d\n",(int)(path.size()));for (int x:path) printf("%d ",x);putchar(10);return 0;
}