2023NOIP A层联测26 T3 tour

有意思的树上主席树。

思路

首先考虑一个点 \(p\) 能计入答案的情况，就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。

记录一个点 \(x\) 到根路径上的前缀和为 \(s_x\)，对于两条路径，我们分类讨论：

第一条，合法条件为 \(s_x-s_p \ge a_p\)，也就是 \(s_p+a_p \le s_x\)。左边的是一个关于 \(p\) 的式子，我们把它放到某个数据结构里面，查询一条链上小于等于给定值的值的个数，如果树给定，这显然是可以通过主席树来做的。

具体来说，每个点继承它父亲的版本，最后把两个版本一减就好了。

第二条，我们记录 lca 的父亲为 \(z\)，那么合法条件为 \(s_x-s_z+s_p-s_{lca}-a_p \ge a_p\)，也就是 \(2 \times a_p-s_p \le s_x-s_z-s_{lca}\)。

左边是一个关于 \(p\) 的式子，右边是一个定值，也可以用类似的方法通过主席树求出。

那么允许离线的方法就很明显了，先建出树，然后对于每个点维护两棵主席树，分别表示第一种和第二种情况，然后查询的时候拆成两条路径分别查询即可（注意不要重复算 lca）。

现在考虑在线。一个经典的方法是启发式合并，由于答案和树的形态无关，可以每次把 size 小的连通块合并到 size 大的连通块上，对于 size 小的那个连通块，我们暴力重构需要维护的信息，包括倍增数组、前缀和数组和主席树。然后正常查询就好了。

启发式合并的复杂度是 \(O(n \log n)\)，再加上重构倍增数组和主席树，复杂度就是 \(O(n \log n \log V)\)。

CODE

#include<bits/stdc++.h>
using namespace std;

#define lch(p) tree[p].ch[0]
#define rch(p) tree[p].ch[1]

const int maxm=5e7+10,maxn=1e5+5;
const int lim=5e8;

struct Tree
{
    int ch[2],siz;
}S1[maxm],S2[maxm];
struct Edge
{
    int to,nxt;
}edge[maxn*2];

int n,S1tot,S2tot,tot,tp,q,la;
int val[maxn],head[maxn],fa[maxn],sz[maxn],rt1[maxn],rt2[maxn],f[maxn][25],sum[maxn],dep[maxn];

void add(int x,int y)
{
    tot++;
    edge[tot].to=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}

int findroot(int x){return fa[x]==x?x:fa[x]=findroot(fa[x]);}

void insert(Tree *tree,int &tot,int &p,int l,int r,int x)
{
    tree[++tot]=tree[p];
    p=tot;
    if(l==r){tree[p].siz++;return ;}
    int mid=l+r>>1;
    if(mid>=x) insert(tree,tot,lch(p),l,mid,x);
    else insert(tree,tot,rch(p),mid+1,r,x);
    tree[p].siz=tree[lch(p)].siz+tree[rch(p)].siz;
}
int query(Tree *tree,int p,int lp,int l,int r,int lx,int rx)
{
    if(lx<=l&&r<=rx) return tree[p].siz-tree[lp].siz;
    if(rx<l||r<lx) return 0;
    int mid=l+r>>1;
    return query(tree,lch(p),lch(lp),l,mid,lx,rx)+query(tree,rch(p),rch(lp),mid+1,r,lx,rx);
}

void dfs(int u,int fa,int d)
{
    dep[u]=d;
    f[u][0]=fa;
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
    rt1[u]=rt1[fa],rt2[u]=rt2[fa];
    sum[u]=sum[fa]+val[u];
    insert(S1,S1tot,rt1[u],-lim,lim,sum[u]+val[u]);
    insert(S2,S2tot,rt2[u],-lim,lim,2*val[u]-sum[u]);
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,u,d+1);
    }
}

int Lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}

int main()
{
    scanf("%d",&tp);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        fa[i]=i,sz[i]=1,sum[i]=val[i],dep[i]=1;
        insert(S1,S1tot,rt1[i],-lim,lim,val[i]*2);
        insert(S2,S2tot,rt2[i],-lim,lim,val[i]);
    }

    while(q--)
    {
        int op,u,v;
        scanf("%d%d%d",&op,&u,&v);
        if(tp) u=u^la,v=v^la;
        if(!op)
        {
            int fu=findroot(u),fv=findroot(v);
            if(sz[fu]<sz[fv]) swap(u,v),swap(fu,fv);
            fa[fv]=fu,sz[fu]+=sz[fv];
            dfs(v,u,dep[u]+1);
            add(u,v);
            add(v,u);
        }
        else
        {
            int lca=Lca(u,v);
            int z=f[lca][0];
            la=query(S1,rt1[u],rt1[z],-lim,lim,-lim,sum[u])+query(S2,rt2[v],rt2[lca],-lim,lim,-lim,sum[u]-sum[lca]-sum[z]);
            printf("%d\n",la);
        }
    }
}