lca

critnos · 2022-09-06 18:18:25 · 个人记录

namespace lca
{
    const int mxn=5e5+5;
    struct node
    {
        int x,nxt;
    }a[mxn*2];
    int head[mxn];
    int n,cnt;
    void add_(int x,int y)
    {
        a[++cnt].x=y;
        a[cnt].nxt=head[x];
        head[x]=cnt;
    }
    void add(int x,int y)
    {
        add_(x,y),add_(y,x);
    }
    int f[mxn];
    int dcnt;
    #define pr pair<int,int>
    struct Word_RMQ
    {
        #define w 32
        #define u unsigned
        #define be(x) ((x>>5)+1)
        #define l(x) ((x-1<<5)+(x==1))
        #define r(x) min(N,((x<<5)-1))
        #define bm mxn/w+5
        int N;
        pr *a;
        pr ST[int(log2(bm)+1)][bm];
        pr pre[mxn],nxt[mxn];
        struct node
        {
            u st[w+1];
            pr *p;
            inline pr ask(int l,int r)
            {
                return p[l+__builtin_ctz(st[r]>>l-1)];
            }
            void init(pr *p_,int len)
            {
                p=p_;
                int i,top=0;
                int stack[w+1];
                for(i=1;i<=len;i++)
                {
                    st[i]=st[i-1];
                    while(top&&p[i]<p[stack[top]])
                        st[i]-=1u<<stack[top--]-1;
                    stack[++top]=i,st[i]+=1u<<i-1;
                }
            }
        }k[bm];
        void build(pr A[],int n)
        {
            a=A,N=n;
            int i,j,cnt=0;
            for(i=1;;i++)
            {
                k[i].init(a+l(i)-1,r(i)-l(i)+1);
                for(j=l(i)+1,pre[l(i)]=a[l(i)];j<=r(i);j++)
                    pre[j]=min(pre[j-1],a[j]);
                for(j=r(i)-1,nxt[r(i)]=a[r(i)];j>=l(i);j--)
                    nxt[j]=min(nxt[j+1],a[j]);
                ST[0][i]=pre[r(i)];
                cnt++;
                if(r(i)==n) break;
            }
            for(j=1;(1<<j)<=cnt;j++)
                for(i=1;i+(1<<j)-1<=cnt;i++)
                    ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
        }
        inline pr STask(int L,int R)
        {
            if(L>R) return make_pair(INT_MAX,INT_MAX);
            int k=__lg(R-L+1);
            return min(ST[k][L],ST[k][R-(1<<k)+1]);
        }
        inline pr ask(int L,int R)
        {
            if(L>R) return make_pair(INT_MAX,INT_MAX);
            if(be(L)==be(R)) return k[be(L)].ask(L-l(be(L))+1,R-l(be(L))+1);
            return min({STask(be(L)+1,be(R)-1),pre[R],nxt[L]});
        }
        #undef w
        #undef l
        #undef r
    }ds;
    pr st[mxn];
    void dfs(int d,int deep,int fa)
    {
        st[dcnt]=make_pair(deep,fa),f[d]=++dcnt;
        for(int i=head[d];i;i=a[i].nxt)
            if(!f[a[i].x])
                dfs(a[i].x,deep+1,d);
    }
    int asklca(int l,int r)
    {
        if(l==r) return l;
        l=f[l],r=f[r];
        if(l>r) swap(l,r);
        return ds.ask(l,r-1).second;
    }
    void init(int N,int s)
    {
        dfs(s,1,0);
        ds.build(st,n=N);
    }
}