T1 大数

Description

给定一个长度为 $n$ 的十进制数 s 和一个质数 $p$ 。 $q$ 次询问，每次给定 $l\ r$ ，询问有多少十进制数 s[x:y] $(l\leq x\leq y\leq r)$ 能被 $p$ 整除。
$1\leq n,q\leq 2\times 10^5,p\leq 2\times 10^9$

Solution

设

$h_i=\sum_{j=1}^{i}s[j]\times 10^{j-1}$

则十进制下 s[x:y] 能被 $p$ 整除的条件为：

$h_{x-1}\times 10^{y-x+1}\equiv h_y\pmod{p}$

转化一下就变成了

$\frac{h_{x-1}}{10^{x-1}}\equiv \frac{h_y}{10^{y}} \pmod{p}$

变成了统计区间内相等的数的对数，使用莫队可以做到 $n\sqrt{n}$ 。
需要注意的是：这个屑题没有保证 p 与 10 的关系，也就是说 p 可以是 2 或者 5。此时就无法使用上述做法了（10 无逆元），应该单独特判。

Code

const int N=2e5+5;
using namespace std;
int p,m;
int h[N],o[N],bel[N],inv[N],ans[N];
char s[N];
struct Query{
    int l,r,id;
    bool operator <(const Query &b)const{
        if(bel[l]==bel[b.l]) return r<b.r;
        return l<b.l;
    }
}q[N];


int Q(int b,int t){
    int ret=1;
    for(int i=1;i<=t;i<<=1,b=1ll*b*b%p)
        if(i&t) ret=1ll*ret*b%p;
    return ret;
}
namespace Sub1{
    long long now,t[N];
    void add(int v){now+=1ll*t[v],++t[v];}
    void del(int v){--t[v],now-=1ll*t[v];}
    void solve(){
        int L=1,R=0;                    // [1,L) deled [1,R] added
        for(int i=1;i<=m;++i){
            --q[i].l;
            while(L<q[i].l) del(h[L++]);
            while(L>q[i].l) add(h[--L]);
            while(R<q[i].r) add(h[++R]);
            while(R>q[i].r) del(h[R--]);
            ans[q[i].id]=now;
        }
    }
}
namespace Sub2{
    bool two(char c){return (c-'0')%2==0;}
    bool fiv(char c){return (c-'0')%5==0;}
    void solve(){
        int L=1,R=0,cnt2=0,cnt5=0,now2=0,now5=0;
        for(int i=1;i<=m;++i){
            while(R<q[i].r){
                ++R;
                if(two(s[R])) ++cnt2,now2+=R-L+1;
                if(fiv(s[R])) ++cnt5,now5+=R-L+1;
            }
            while(R>q[i].r){
                if(two(s[R])) --cnt2,now2-=R-L+1;
                if(fiv(s[R])) --cnt5,now5-=R-L+1;
                --R;
            }
            while(L<q[i].l){
                now2-=cnt2,now5-=cnt5;
                if(two(s[L])) --cnt2;
                if(fiv(s[L])) --cnt5; 
                ++L;
            }
            while(L>q[i].l){
                --L;
                if(two(s[L])) ++cnt2;
                if(fiv(s[L])) ++cnt5;
                now2+=cnt2,now5+=cnt5;
            }
           
            ans[q[i].id]=p==2?now2:now5;
        }
    }
}
int main(){

    scanf("%d",&p);
    scanf("%s",s+1);
    int n=strlen(s+1);
    inv[0]=1;
    for(int i=1,iv=Q(10,p-2);i<=n;++i)
        h[i]=(10ll*h[i-1]+s[i]-'0')%p,inv[i]=1ll*inv[i-1]*iv%p;
    for(int i=0;i<=n;++i)
        h[i]=1ll*inv[i]*h[i]%p,o[i]=h[i];
    sort(o,o+n+1);
    for(int i=0;i<=n;++i)
        h[i]=lower_bound(o,o+n+1,h[i])-o;
    scanf("%d",&m);
    int B=sqrt(n);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    for(int i=1;i<=n;++i) 
        bel[i]=(i-1)/B+1;
    sort(q+1,q+m+1);
    if(p==2||p==5) Sub2::solve();
    else Sub1::solve();
    for(int i=1;i<=m;++i)
        w(ans[i]);
    return 0;
}

T2 序列

Description

给定长度为 $n$ 的序列 $\{a\}$ 。$q$ 次询问，每次给定两个数 $l\ r$ ，求 $a[l:r]$ 的所有子串的最小值之和。
$1\leq n,q\leq 10^5$

Solution

这个题也算是一个 trick 吧。
设 f[p] 表示以 p 为右端点，左端点位于 $1\sim p$ 之间的所有子串的最小值之和。即：

$f[p]=\sum\limits_{i=1}^{p}\min\{a_i,\cdots,a_p\}$

需要注意的是，这个东西是不具有通常意义上的可差分性的。也就是说 f[r]-f[l-1] 是无意义的。
但是我们有办法让它可以差分。考虑 f[p] 的递推式。设 pre[p] 表示 $p$ 之前的第一个比它小的位置（若均比它大则设为 $0$ ）。那么有

$f[p]=f[\text{pre}_p]+a[p]*(p-\text{pre}_p)$

所以 f[p]-f[pre[p]] 是具有可差分性的，它的含义是右端点在 p ，左端点在 $\text{pre}_p+1\sim p$ 的所有子串的最小值之和。
既然 f[p]-f[pre[p]] 可差分，那么 f[pre[p]]-f[pre[pre[p]]] 也具有可差分性......
重要发现：我们找到 $[l,r]$ 中的最小值位置 $x$ ，那么 f[r]-f[x] 的含义是右端点在 $r$ ，左端点在 $x+1\sim r$ 的所有子串的最小值之和。
为什么呢？因为 $x$ 是区间最小值位置，所以一直走 pre 一定可以走到 $x$ 。

于是我们不妨先考虑左端点在 $x$ 以右的所有区间的贡献：

$\sum_{i=x+1}^{r}(f[i]-f[x])$

这式子明显可以前缀和优化。设 g[p] 是 f 的前缀和，可得上式为：

$g[r]-g[x]-(r-x)*f[x]$

于是这个贡献就可以 $\mathcal{O}(1)$ 计算出来。
右端点在 $x$ 以左的区间可以用类似的方法计算，不赘述。
剩下的右端点在 $x$ 以右，左端点在 $x$ 以左的区间的贡献就是 $(r-x+1)*(x-l+1)*a[x]$ 。
于是就可以 $\mathcal{O}(1)$ 回答每个询问了。

复杂度 $\mathcal{O}(n\log_2n+q)$。

Code

const int N=1e5+5;
using namespace std;
int n,m;
int s[N],lg[N],suf[N],pre[N],f[N][20];
long long a[N],gl[N],gr[N],fl[N],fr[N];
int check(int x,int y){return a[x]<a[y]?x:y;}
int query(int x,int y){
   int k=lg[y-x+1];
   return check(f[x][k],f[y-(1<<k)+1][k]);
}
int main(){

   r(n,m);
   for(int i=1;i<=n;++i) r(a[i]),f[i][0]=i;
   for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
   for(int j=1;j<=lg[n];++j)
   for(int i=1;i+(1<<j)-1<=n;++i)
       f[i][j]=check(f[i][j-1],f[i+(1<<j-1)][j-1]);
   int top=0;
   for(int i=1;i<=n;++i){
       while(top&&a[s[top]]>=a[i]) suf[s[top]]=i,--top;
       pre[i]=s[top],s[++top]=i;
   }
   while(top) 
       pre[s[top]]=s[top-1],suf[s[top]]=n+1,--top;
   for(int i=1;i<=n;++i) fl[i]=fl[pre[i]]+1ll*a[i]*(i-pre[i]),gl[i]=gl[i-1]+fl[i];
   for(int i=n;i>=1;--i) fr[i]=fr[suf[i]]+1ll*a[i]*(suf[i]-i),gr[i]=gr[i+1]+fr[i];
   for(int i=1,x,y;i<=m;++i){
       r(x,y);int pos=query(x,y);
       long long ans=1ll*(pos-x+1)*(y-pos+1)*a[pos];
       ans=ans+(gl[y]-gl[pos]-1ll*fl[pos]*(y-pos));
       ans=ans+(gr[x]-gr[pos]-1ll*fr[pos]*(pos-x));
       w(ans);
   }
   return 0;
}

T3 网络

Description

给定一棵 $n$ 个点的树，$m$ 次操作，分别为三种类型：

• 加入路径 $u\rightarrow v$ ，路径重要度为 $v$ 。
• 撤销第 $k$ 次操作时加入的路径。
• 询问所有不经过 $x$ 的路径中重要度的最大值。若未经过路径，输出 -1 。

$n,m\leq 10^5$

Solution

整体二分，仅在重要度大于 $v$ 的路径上修改（包含加入/撤销）。询问时统计目前经过该点的路径总数，并与当前加入的路径总条数进行比较再决定是左递归还是右递归。
问题转化为路径覆盖和单点查询，可以通过树上差分再次转化为单点修改子树查询。使用树状数组维护。
复杂度 $\mathcal{O}(m\log^2_2n)$ 。

还有一种 $\mathcal{O}(m\log_2n)$ 的线段树二分做法。
先将路径排序，并建立一棵线段树，叶子节点维护排序后的路径（也就是叶子结点的权值单调）。普通的节点就维护两个子节点的路径的路径交。再按照时间顺序插入/撤销/查询即可。

博主本人想训练整体二分，故代码采用的第一种方法。

Code

const int N=2e5+5;
using namespace std;
int n,m,dfn,num;
int in[N],out[N],dep[N],f[N][20];
int o[N],head[N],nt[N<<1],to[N<<1];
struct Query{
    int tp,a,b,v,val,id,ans;
    Query(int id=0,int tp=0,int a=0,int b=0,int v=0,int val=0):
        id(id),tp(tp),a(a),b(b),v(v),val(val) {}
    bool operator <(const Query &o)const{
        return id<o.id;
    }
}q[N],Qt[N];
void Add(int x,int y){
    ++num;nt[num]=head[x];head[x]=num;to[num]=y;
    ++num;nt[num]=head[y];head[y]=num;to[num]=x;
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) x^=y^=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];
}
namespace BIT{
#define lowb(x) (x&-x)
    int t[N]; //various
    void Add(register int p,int v){
        while(p<=n) t[p]+=v,p+=lowb(p);
    }
    int Get(register int p){
        int ret=0;
        while(p) ret+=t[p],p-=lowb(p);
        return ret;
    }
    void modify(int x,int y,int v){
        int z=LCA(x,y);Add(in[x],v),Add(in[y],v),Add(in[z],-v);
        if(f[z][0]) Add(in[f[z][0]],-v);
    }
    int query(int x){
        return Get(out[x])-Get(in[x]-1);
    }
#undef lowb
}
using BIT::modify;
using BIT::query;
void solve(int QL,int QR,int VL,int VR){
    if(QL>QR) return;
    if(VL==VR){
        for(int i=QL;i<=QR;++i) 
            if(q[i].tp==2) q[i].ans=o[VL];
        return;
    }
    int mid=VL+VR>>1,path=0,tl=QL,tr=QR;
    for(int i=QL;i<=QR;++i)
        if(q[i].tp<2)
            if(q[i].v<=o[mid]) Qt[tl++]=q[i];
            else modify(q[i].a,q[i].b,q[i].val),Qt[tr--]=q[i],path+=q[i].val;
        else{
            //if(QL==1&&QR==23) cerr<<q[i].a<<" "<<query(q[i].a)<<endl;
            if(query(q[i].a)==path) Qt[tl++]=q[i];
            else Qt[tr--]=q[i];
        }
    for(int i=tr+1;i<=QR;++i)
        if(Qt[i].tp<2) modify(Qt[i].a,Qt[i].b,-Qt[i].val);
    for(int i=QL;i<tl;++i) q[i]=Qt[i];
    reverse(Qt+tr+1,Qt+QR+1);
    for(int i=QR;i>tr;--i) q[i]=Qt[i];
    solve(QL,tl-1,VL,mid);solve(tr+1,QR,mid+1,VR);
}
void dfs(int p,int fa){
    f[p][0]=fa;dep[p]=dep[fa]+1;in[p]=++dfn;
    for(int i=0;f[p][i];++i) f[p][i+1]=f[f[p][i]][i];
    for(int i=head[p];i;i=nt[i])
        if(to[i]^fa) dfs(to[i],p);
    out[p]=dfn;
}
int main(){

    r(n,m);
    for(int i=1,x,y;i<n;++i)
        r(x,y),Add(x,y);
    dfs(1,0);
    int cnt=0;
    for(int i=1,type;i<=m;++i){
        r(type);int a,b,v,t;
        if(type==0) r(a,b,v),q[i]=Query(i,type,a,b,v,1),o[++cnt]=v;
        if(type==1) r(t),q[i]=q[t],q[i].val=-1,q[i].id=i,q[i].tp=type;
        if(type==2) r(a),q[i]=Query(i,type,a);
    }
    o[++cnt]=-1;
    sort(o+1,o+cnt+1);
    solve(1,m,1,cnt);
    sort(q+1,q+m+1);
    for(int i=1;i<=m;++i)
        if(q[i].tp==2) w(q[i].ans);
    return 0;
}

T4 最小公倍数

Description

给定一张 $n$ 个点 $m$ 条边的图，每条边上有两个属性 $e_a,e_b$ 。$q$ 次询问，每次询问能否找到一条从 $u$ 到 $v$ 的路径，满足 $\max\{e_a\}=a$ ，$\max\{e_b\}=b$ 。路径不要求是简单路径。
$n,q\leq 5\times 10^4,m\leq 10^5$

Solution

据说是个蛮经典的 trick 。
如果只有 $\max\{e_a\}=a$ 这个要求，我们可以按升序依次加边，通过并查集维护两点连通性以及连通块内最大 $e_a$ 值。离线询问即可快速处理。
但是现在有两个要求，怎么办呢？

对于这种有两个限制的，我们可以分块来处理。
首先按照第一关键字（这里选择 $e_a$ ）排序后分块，并将询问挂到块上。对于第 $i$ 个询问，我们把它挂到第一个 $e_a$ 大于 $a_i$ 的点对应的块上。所以对于一个询问而言，其对应的块的所有前缀的 $e_a$ 都是满足条件的。当处理到第 $k$ 个块时，将 $1\sim k-1$ 的块内的元素按照第二关键字（这里选择 $e_b$ ）排序，并将挂在这个块上的所有询问按照 $b_i$ 排序。这样对于块外的元素我们可以双指针添加（因为第一关键字已经满足条件了），对于块内的元素（有的第一关键字还未满足条件）暴力添加/撤销。恰好我们的并查集是可以支持撤销操作的。于是问题顺利解决。

复杂度 $\mathcal{O}((q+m)\sqrt{m}\log_2{m})$ 。好像有点爆炸，但应该是跑不满的。

Code

const int N=5e4+5,M=1e5+5;
using namespace std;
int n,m,Q;
struct edge{
    int u,v,a,b,id;
    edge(int u=0,int v=0,int a=0,int b=0,int id=0):
        u(u),v(v),a(a),b(b),id(id) {}  
}e[M];
vector<edge>q[M];
namespace Union{
    int top;
    int f[N],sz[N],mxa[N],mxb[N];
    edge draw[M];
    void Init(){
        for(int i=1;i<=n;++i)
            f[i]=i,mxa[i]=mxb[i]=-1,sz[i]=1;
    }
    int Find(int x) {return f[x]==x?x:Find(f[x]);}
    void Link(int u,int v,int a,int b,int tp){
        u=Find(u),v=Find(v);
        if(u==v){
            if(tp) draw[++top]=edge(u,0,mxa[u],mxb[u]);
            mxa[u]=max(mxa[u],a);
            mxb[u]=max(mxb[u],b);
            return;
        }
        if(sz[u]<sz[v]) swap(u,v); 
        if(tp) draw[++top]=edge(u,v,mxa[u],mxb[u]);
        sz[u]+=sz[v];f[v]=u;
        mxa[u]=max(mxa[u],max(mxa[v],a));
        mxb[u]=max(mxb[u],max(mxb[v],b));
    }
    void Back(){
        for(;top;--top){
            edge t=draw[top];
            if(t.v==0){
                mxa[t.u]=t.a;mxb[t.u]=t.b;
                continue;
            }
            sz[t.u]-=sz[t.v];f[t.v]=t.v;
            mxa[t.u]=t.a,mxb[t.u]=t.b;
        }
    }
}
using namespace Union;
bool cmpa(edge x,edge y){return x.a<y.a;}
bool cmpb(edge x,edge y){return x.b<y.b;}
int Min[M],ans[N];
int main(){

    r(n,m);
    for(int i=1,u,v,a,b;i<=m;++i)
        r(u,v,a,b),e[i]=edge(u,v,a,b,i);
    sort(e+1,e+m+1,cmpa); 
    int B=400;
    for(int i=1,id=1;i<=m;i+=B,++id){
        int up=min(i+B-1,m);
        Min[id+1]=0x3f3f3f3f;
        Min[id]=e[i].a;
    }
    r(Q);
    for(int i=1,u,v,a,b;i<=Q;++i){
        r(u,v,a,b);
        for(int id=2;;++id)
            if(Min[id]>a) {q[id-1].push_back(edge(u,v,a,b,i));break;}
    }
    for(int i=1,id=1;i<=m;i+=B,++id){
        if(!q[id].size()) continue;
        Init();
        int up=min(i+B-1,m);
        sort(q[id].begin(),q[id].end(),cmpb);
        sort(e+1,e+i,cmpb);
        int cnt=1;
        for(auto now:q[id]){
            while(cnt<i&&e[cnt].b<=now.b)
                Link(e[cnt].u,e[cnt].v,e[cnt].a,e[cnt].b,0),++cnt;
            for(int j=i;j<=up;++j)
                if(e[j].a<=now.a&&e[j].b<=now.b)
                    Link(e[j].u,e[j].v,e[j].a,e[j].b,1);
            int u=Find(now.u),v=Find(now.v);
            ans[now.id]=(u==v)&&(mxa[u]==now.a)&&(mxb[u]==now.b);
            Back();
        }
    }
    for(int i=1;i<=Q;++i)
        puts(ans[i]?"Yes":"No");
    return 0;
}

T5 矿区

Description

给定一张 $n$ 个点 $m$ 条边的平面图，平面图上有若干个平面块，每个块的矿量是面积 $s$ 的平方。现在有 $q$ 个开采计划，每个开采计划会逆时针给定 $c$ 个点，表示询问这 $c$ 个点围成的封闭图形中平面块的矿量之和与平面块的面积之和的比值。要求给出最简分数形式。

$n,q\leq 2\times 10^5,m\leq 3n-6,\sum c\leq 2\times 10^6$ 。点的坐标是整数。无多余的边。保证每次查询的区域至少包含一个平面块，且平面块一定连通。保证答案不大于 $2^{63}-1$ 。

Solution

有一个很好的思路是平面图转对偶图。把平面图上的每个面转为点，点权为面积。然后构造出原图的任意一棵生成树（以无穷域为根），然后在生成树上计算答案。
接下来就是如何转对偶图、如何找生成树、如何计算答案了。方法大战。
首先是如何转对偶图。将每条边拆为两条单向边，这样每条边都属于一个面（最外层的边属于无穷域面）。将边挂在点上，并将点上的边极角排序。当找 $u\rightarrow v$ 与哪些边属于一个面时，我们只需要找到以 $v$ 为起点的边中 $v\rightarrow u$ 的前驱即可。记录 nxt[p] 表示逆时针方向上 $p$ 这条边所在的面的后一条边，可以发现这个前驱就是 nxt 。
然后是如何找生成树。先给每个面计算面积，除了无穷域外，面积均为正数。我们将无穷域设为根。相邻两个面在对偶图中相连当且仅当共边。于是枚举原图中的每条边，将正反边所属的面相连即可。
最后是如何计算答案。造成答案的一定是一个点集，点集的贡献可以由子树之间加加减减来求得。故首先在生成树上做子树和。对于给定的边 $u\rightarrow v$ ，如果是非树边直接忽略；如果这条边所在的面是反边的子节点，那么我们直接加上这个点的答案；否则，我们就减去这个点的反边的面的答案。这部分可能有些抽象，但画个图就很好理解。

复杂度大概是 $\mathcal{O}((m+q)\log_2m)$ 的吧。

Code

const int N=2e5+5,M=12e5+5;
using namespace std;
int n,m,Q,rt,cnt,num,tot=1;
int f[M<<1],nxt[M<<1],pos[M<<1],vis[M<<1],intr[M<<1];
long long s[M<<1],fz[M<<1],fm[M<<1];
struct vec{
    int x,y;
    vec(int x=0,int y=0):x(x),y(y) {}
    vec operator -(const vec &b)const{return vec(x-b.x,y-b.y);}
}p[N];
long long crs(vec a,vec b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
const double eps=1e-9;
int dcmp(double v){
    return fabs(v)<eps?0:1;
}
struct edge{
    int id,u,v;double d;
    edge(int id=0,int u=0,int v=0,double d=0):
        id(id),u(u),v(v),d(d) {}
    bool operator <(const edge &b)const{
        return dcmp(b.d-d)==0?v<b.v:d<b.d;
    }
}l[M<<1];
vector<edge>line[N];
void add(int a,int b){
    ++tot;l[tot]=edge(tot,a,b,atan2((p[b]-p[a]).y,(p[b]-p[a]).x));line[a].push_back(l[tot]);
}
int nt[M<<2],to[M<<2],val[M<<2],head[M<<1];
void Add(int x,int y,int z){
    ++num;nt[num]=head[x];head[x]=num;to[num]=y;val[num]=z;
    ++num;nt[num]=head[y];head[y]=num;to[num]=x;val[num]=z;
}
void build(){
    for(int i=1;i<=n;++i) sort(line[i].begin(),line[i].end());
    for(int i=2;i<=tot;++i){
        int a=l[i].v;
        vector<edge>::iterator p=lower_bound(line[a].begin(),line[a].end(),l[i^1]);
        if(p==line[a].begin()) p=line[a].end();
        nxt[i]=(*(--p)).id;
    }
    for(int i=2;i<=tot;++i){
        if(pos[i]) continue;
        pos[i]=pos[nxt[i]]=++cnt;
        for(int j=nxt[i];l[j].v!=l[i].u;pos[j=nxt[j]]=cnt)
            s[cnt]+=crs((p[l[j].u]-p[l[i].u]),(p[l[j].v]-p[l[i].u]));
        if(s[cnt]<=0) rt=cnt;
    }
    for(int i=2;i<=tot;++i)
        Add(pos[i],pos[i^1],i);
}
void dfs(int p,int fa){
    f[p]=fa,fz[p]=1ll*s[p]*s[p],fm[p]=s[p]*2;vis[p]=1;
    for(int i=head[p];i;i=nt[i])if(!vis[to[i]]){
        int v=to[i];dfs(v,p);
        fm[p]+=fm[v];fz[p]+=fz[v];
        intr[val[i]]=intr[val[i]^1]=1;
    }
}
int q[N*10];
long long GCD(long long a,long long b){
    return !b?a:GCD(b,a%b);
}
int main(){

    r(n,m,Q);
    for(int i=1,x,y;i<=n;++i) 
        r(x,y),p[i]=vec(x,y);
    for(int i=1,x,y;i<=m;++i)
        r(x,y),add(x,y),add(y,x);
    build();dfs(rt,0);
    long long ans1=0,ans2=0,c=0;
    for(int i=1;i<=Q;++i){
        r(c);c=(c+ans1)%n+1;
        for(int j=1,x;j<=c;++j) r(x),q[j]=(x+ans1)%n+1;
        q[c+1]=q[1],ans1=ans2=0;
        for(int j=1,x,y;j<=c;++j){
            x=q[j],y=q[j+1];
            edge now=edge(0,x,y,atan2((p[y]-p[x]).y,(p[y]-p[x]).x));
            auto p=lower_bound(line[x].begin(),line[x].end(),now);
            int id=(*p).id;
            if(!intr[id]) continue;
            if(f[pos[id]]==pos[id^1]) ans1+=fz[pos[id]],ans2+=fm[pos[id]];
            else ans1-=fz[pos[id^1]],ans2-=fm[pos[id^1]];
        }
        long long gcd=GCD(ans1,ans2);
        ans1/=gcd,ans2/=gcd;
        w(ans1,' '),w(ans2);
    }
    return 0;
}

T6 树

Description

小 A 想做一棵大树。一开始时，小 A 只有一棵节点数为 $n$ 的以 $1$ 为根模板树。小 A 决定用模板树来构建一棵大树。构建过程如下：
1、将模板树复制为初始的大树。
2、 以下(2.1)(2.2)(2.3)步循环执行 $m$ 次
（2.1）选择两个数字 $a,b$ ，其中 $1 \leq a \leq n$, $1 \leq b \leq \text{当前大树的结点数}$。
（2.2）将模板树中以结点 $a$ 为根的子树复制一遍，挂到大树中结点 $b$ 的下方(也就是说，模板树中的结点 $a$ 为根的子树复制到大树中后，将成为大树中结点 $b$ 的子树)。
（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。假设在进行 2.2 步之前大树有 $L$ 个结点，模板树中以 a 为根的子树共有 $C$ 个结点，那么新加入模板树的 $C$ 个结点在大树中的编号将是 $L+1,L+2,\cdots,L+C$ ；大树中这 $C$ 个结点编号的大小顺序和模板树中对应的 $C$ 个结点的大小顺序是一致的。
现在给定你模板树，以及 $m$ 次操作的具体情况。$q$ 次询问，每次询问最后的大树中两点间的距离。
$n,m,q\leq 10^5$

Solution

@$%^&，文明靠大家。
树套树。我们把 $m$ 次操作看成 $m$ 个虚拟节点，每个节点对应模板树中的一个子树。
求两点间的距离需要我们实现求深度/到根节点距离和求 LCA 。我们在模板树和大树上对应维护就行了。毕竟这两个东西都是可以在线求的。
我们需要两个前置操作：getpos(u) 和 getnode(u) ，分别是找到 $u$ 对应的虚拟节点和 $u$ 在模板树上的对应节点。
记录每个虚拟节点所占据的编号区间即可二分实现 getpos 。getnode 实际上是求子树内编号第 $k$ 小，可以通过主席树解决。
剩下的就不停往上跳/特判就行啦。写起来还是蛮爽的。

复杂度 $\mathcal{O}((m+q)\log_2m)$ 。要注意常数。

Code

const int N=1e5+5,M=22;
using namespace std;
namespace SEG{
#define mid (l+r>>1)
    int tot,t[N<<5],lc[N<<5],rc[N<<5];
    void modify(int pre,int &p,int l,int r,int pos){
        p=++tot;t[p]=t[pre]+1;
        lc[p]=lc[pre],rc[p]=rc[pre];
        if(l==r) return;
        if(mid>=pos) modify(lc[pre],lc[p],l,mid,pos);
        else modify(rc[pre],rc[p],mid+1,r,pos);
    }
    int query(int pre,int suf,int l,int r,int pos){
        if(l==r) return l;
        if(t[lc[suf]]-t[lc[pre]]>=pos) return query(lc[pre],lc[suf],l,mid,pos);
        else return query(rc[pre],rc[suf],mid+1,r,pos-(t[lc[suf]]-t[lc[pre]]));
    }
#undef mid
}
namespace TEM{
    int n,dfn;
    int S[N],T[N],sz[N],rt[N],idx[N],dep[N],f[N][M];
    vector<int>c[N];
    void DFS(int p,int fa){
        S[p]=++dfn;idx[dfn]=p;
        f[p][0]=fa;dep[p]=dep[fa]+1;sz[p]=1;
        for(int i=0;f[p][i];++i) f[p][i+1]=f[f[p][i]][i];
        for(auto u:c[p])
            if(u^fa) DFS(u,p),sz[p]+=sz[u];
        T[p]=dfn;
    }
    int LCA(int x,int y){
        if(dep[x]<dep[y]) x^=y^=x^=y;
        for(int i=20;i>=0;--i)
            if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
        return f[x][0];
    }
    int dis(int x,int y){
        int z=LCA(x,y);
        return dep[x]+dep[y]-2*dep[z];
    }
    void build(){
        for(int i=1,x,y;i<n;++i)
            r(x,y),c[x].push_back(y),c[y].push_back(x);
        DFS(1,0);
        for(int i=1;i<=n;++i)
            SEG::modify(rt[i-1],rt[i],1,n,idx[i]);
    }
}
using TEM::rt;
namespace BIG{
    int m,cnt;
    int lg[N],dep[N],link[N],inte[N],f[N][M];
    long long S[N],T[N],dis[N],tot;
    int getpos(long long x){
        int l=1,r=cnt;
        while(l<=r){
            int mid=l+r>>1;
            if(x>=S[mid]&&x<=T[mid]) return mid;
            else if(x>T[mid]) l=mid+1;
            else r=mid-1;
        }
        assert(-1);
    }
    int getnode(long long x,int pos=0){            //不要无脑求 pos 。卡常
        if(!pos) pos=getpos(x);
        return SEG::query(rt[TEM::S[inte[pos]]-1],rt[TEM::T[inte[pos]]],1,TEM::n,x-S[pos]+1);
    }
    void build(){
        for(int i=1;i<=m;++i) lg[i]=lg[i-1]+((1<<lg[i-1])==i);
        S[cnt=1]=1,T[1]=tot=TEM::n;dep[1]=1;inte[1]=1;
        for(int i=1,a,pos,id;i<=m;++i){
            long long b;
            r(a,b);pos=getpos(b);id=getnode(b,pos);
            ++cnt;
            link[cnt]=id;inte[cnt]=a;
            S[cnt]=tot+1;T[cnt]=(tot+=TEM::sz[a]);
            f[cnt][0]=pos,dep[cnt]=dep[pos]+1;
            dis[cnt]=dis[pos]+TEM::dep[id]-TEM::dep[inte[pos]]+1;
            for(int i=0;f[cnt][i];++i) f[cnt][i+1]=f[f[cnt][i]][i];
        }
    }
    int LCA(int x,int y){
        if(dep[x]<dep[y]) x^=y^=x^=y;
        for(int i=20;i>=0;--i)
            if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
        return f[x][0];
    }
    int jump(int x,int h){
        while(h){
            int y=f[x][lg[h]-1];
            h-=(dep[x]-dep[y]);x=y;
        }
        return x;
    }
    long long solve(long long x,long long y){
        int px=getpos(x),py=getpos(y),dx=getnode(x,px),dy=getnode(y,py);
        if(px==py) return TEM::dis(dx,dy);
        long long lca=LCA(px,py);
        long long ret=0;
        if(lca==px||lca==py){
            if(lca==py) swap(x,y),swap(px,py),swap(dx,dy);
            ret+=TEM::dep[dy]-TEM::dep[inte[py]],y=py;
            int oldy=y;y=jump(y,dep[y]-dep[lca]-1);
            ret+=dis[oldy]-dis[y]+1;y=link[y];
            ret+=TEM::dis(dx,y);
            return ret;
        }
        ret+=TEM::dep[dx]-TEM::dep[inte[px]],x=px;
        ret+=TEM::dep[dy]-TEM::dep[inte[py]],y=py;
        int oldx=x,oldy=y;
        x=jump(x,dep[x]-dep[lca]-1);
        y=jump(y,dep[y]-dep[lca]-1);
        ret+=dis[oldx]-dis[x]+1+dis[oldy]-dis[y]+1;
        return ret+TEM::dis(link[x],link[y]);
    }
}
int main(){

    int q;r(TEM::n,BIG::m,q);
    TEM::build();BIG::build();
    long long x,y;
    for(int i=1;i<=q;++i)
        r(x,y),w(BIG::solve(x,y));
    return 0;
}

Analysis

5 道数据结构 1 道计算几何 😅 差不多得了
省选还是很重视 trick 的考察。平常多做题。