题解：P17855 [LBA-OI R6 C] 哥德巴赫猜想

· · 题解

来一个好想的单 \log 做法。

其实你直接模拟就行了，每次插入一条链，用一个堆维护三个值 u,v,p，表示 u,v 这条链，p 为这条链上最大值所在的位置。

然后查询操作就是每次取出堆顶加入答案，然后把这条链从最大值处劈成两半，至多往堆里面增加 O(n) 个值，所以复杂度是对的。

查询链上最大值你可以树剖加上 O(n) - O(1) \text{RMQ}，但是没必要。

还是考虑树剖，维护 pre_u 表示 u 到当前重链顶端的最大值所在位置，这样跳重链的时候就做到 O(1)，只有两个在同一条重链上的时候需要查一次 \text{RMQ}，用线段树即可做到一个 \log。

然后这个雷霆卡常也是这题不得不品的一环啊。

两个优化，树剖的递归改成非递归，swap 函数改成用位运算的手写版。

时间复杂度 O((n+m) \log (n+m))。

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define Rep(i,a,b) for (int i=(a);i>=(b);i--)
using namespace std;
namespace fast_IO {
    // fast_IO...
} using namespace fast_IO;
typedef unsigned long long ull;
const int N=1e6+10;

int n,m,a[N],b[N];
string s;
struct node {
    int u,v,p;
    inline friend bool operator < (const node &x,const node &y) {
        return a[x.p]<a[y.p];
    }
};
priority_queue<node> q;
int pre[N],fa[N],siz[N],top[N],son[N],dep[N],dfn[N],idx[N],cnt;
const int B=64;
const int M=N/B+5;
struct RMQ {
    #define calcL(i) ((i-1)<<6|1)
    #define calcR(i) (i<<6)
    pii st[25][M],pre[N],suf[N];
    int up,bel[N];
    ull val[N];
    void build() {
        rep(i,1,n) b[i]=a[idx[i]],bel[i]=((i+63)>>6);
        up=bel[n];
        rep(i,1,up) {
            int L=calcL(i),R=min(n,calcR(i));
            pre[L]={b[L],L},suf[R]={b[R],R};
            rep(j,L+1,R) pre[j]=max(pre[j-1],{b[j],j});
            Rep(j,R-1,L) suf[j]=max(suf[j+1],{b[j],j});
            ull now=0;
            rep(j,L,R) {
                while (now) {
                    int tp=63-__builtin_clzll(now);
                    if (b[j]>=b[L+tp]) now^=(1ull<<tp);
                    else break;
                }
                now|=(1ull<<(j-L)),val[j]=now;
            }
            st[0][i]=pre[R];
        }
        rep(len,1,__lg(up)) rep(l,1,up-(1<<len)+1) {
            st[len][l]=max(st[len-1][l],st[len-1][l+(1<<(len-1))]);
        }
        return ;
    }
    inline int query(int l,int r) {
        int L=bel[l],R=bel[r];
        if (L==R) return l+__builtin_ctzll(val[r]>>(l-calcL(L)));
        pii res=max(suf[l],pre[r]);
        if (L+1<=R-1) {
            L++,R--;int len=__lg(R-L+1);
            res=max(res,max(st[len][L],st[len][R-(1<<len)+1]));
        }
        return res.second;
    }
    #undef calcL
    #undef calcR
    #undef bel
}t;
inline void swap(int &x,int &y) {
    x^=y^=x^=y;
}
inline int query(int u,int v) {
    if (u==v) return u;
    if (dep[u]<dep[v]) swap(u,v);
    int pos=0;
    while (top[u]!=top[v]) {
        if (a[pre[u]]>a[pos]) pos=pre[u];
        u=fa[top[u]];
    }
    int p=idx[t.query(dfn[v],dfn[u])];
    if (a[p]>a[pos]) pos=p;
    return pos;
}
inline int get(int p,int v) {
    if (top[p]==top[v]) return son[p];
    while (top[v]!=top[p]) {
        if (fa[top[v]]==p) return top[v];
        v=fa[top[v]];
    }
    return son[p];
}
int rt[N];
signed main() {
    cin>>n>>m;
    rep(i,1,n) {
        cin>>fa[i];
        if (!fa[i]) rt[i]=i;
        else rt[i]=rt[fa[i]];
        dep[i]=dep[fa[i]]+1,siz[i]=1;
    }
    rep(i,1,n) cin>>a[i];
    Rep(i,n,1) {
        if (i!=fa[i]) {
            siz[fa[i]]+=siz[i];
            if (siz[i]>siz[son[fa[i]]]) son[fa[i]]=i;
        }   
    }
    rep(i,1,n) {
        if (fa[i] and son[fa[i]]==i) continue;
        int pos=0;
        for(int u=i;u;u=son[u]) {
            top[u]=i,dfn[u]=++cnt,idx[cnt]=u;
            if (!pos) pos=u;
            else if (a[u]>a[pos]) pos=u;
            pre[u]=pos;
        }
    }
    t.build();
    ull res=0,cnt=0;
    while (m--) {
        int op;cin>>op;
        if (op==1) {
            int x;cin>>x;
            q.push({rt[x],x,query(rt[x],x)});
        } else {
            if (q.empty()) {
                cnt++;
                continue;
            }
            auto [u,v,p]=q.top();q.pop();
            cnt++,res^=(cnt*a[p]);
            if (u!=p) {
                int x=u,y=fa[p];
                q.push({x,y,query(x,y)});
            }
            if (v!=p) {
                int x=get(p,v),y=v;
                q.push({x,y,query(x,y)});
            }
        }
    }
    cout<<res<<endl;
    return 0;
}