题解[P7357 中位数]

Y_B_X · 2021-10-03 16:20:15 · 题解

题目链接

我不会告诉你我是因为题目背景的头像与我们班主任一毛一样才来写题解的

题意：
给出一棵树，点有点权，每次将一个点的点权异或 1 ，
或给出两个点 u,v ，询问能覆盖 u,v 的路径所形成的序列的中位数最大值。
保证这 u,v 不在一条链上，这里中位数指长为 n 的序列中第 \left\lfloor\frac{n+1}{2}\right\rfloor 大的数。

\text{Step 1}

先看一下这种定义下的中位数的性质：

对于一个序列 S,n=\left|S\right|

设 g_a=|\{i|s_i\geq a,1\leq i\leq n\}|,l_a=|\{i|s_i< a,1\leq i\leq n\}|

则 S 的中位数就是原序列中满足 g_a\leq l_a 的最大的 a

如果把 \geq a 的数设为 1 ，把 <a 的数设为 -1 ，a 是中位数时必须这些 1 与 -1 的和 \geq 0 ，且 a 最大。

由于设成 1 与 -1 的操作在 a 递增时 -1 增多，可以建出一颗主席树来维护。

这套路在 此题 中曾出现过。

\text{Step 2}

对于题目中的满足覆盖 u,v 的路径的中位数最大值，是有单调性的，考虑二分。

对于一个二分的值 mid 我们希望得知：把树上每个点权 \geq mid 的点的 键值 设成 1 ，把点权 <mid 的点的键值 设成 -1 后，查看能覆盖 u,v 路径中 键值的和的最大值 能否 \geq 0 。

由于要覆盖 u,v 且 u,v 不在一条路径上，考虑树上差分。

设 f_x^a=\text{a时x到根路径键值之和}

所以二分时要求的键值的和的最大值就是：

其中 w_x^{a} 代表 a 时 x 的键值。

于是希望对每个 a 维护 dfs 序所代表的点的 f_x^a 值，这样就容易查询子树最大值。

\text{Step 3}

考虑如何用主席树维护 f_x^a 值。

对于 a=0 时，f_x^a=\operatorname{dep}(x) ，即 x 的深度，因为所有点的点权 \geq 0 。

当 a 变大时会导致一些点的键值从 1 变成 -1

那这些点的子树内的所有点的 f^a 值就会 -2 。

由于主席树是以 dfs 序为下标建的，这相当于区间减并可持久化。

这可以用 标记永久化 轻松实现。

\text{Step 4}

现在只剩下最后一个问题：把点权异或 1

开始建主席树时顺便把每个点的点权异或 1 后的值顺带着离散化并建主席树。

由于异或 1 后一个点的点权要么变大一，要么减小一。

设 t_x=2\left\lfloor\frac{x}{2}\right\rfloor+1 ，即不比 x 小的最小的奇数。

那么 a>t_x 的版本无论如何都不发生改变，因为\max(x,x\operatorname{xor}1)\leq t_x

而 a\leq t_x-1 的版本同样不发生变化，因为 \min(x,x\operatorname{xor}1)\geq t_x-1

所以受改动的版本仅有 t_x 一个。

若 x 为奇数， t_x=x , 异或后变小成 x-1 。

那原先 x 的版本中这个点的键值为 1 ，权值变小后要成为 -1

所以将 x 的版本中这个点的子树内所有点的 f 值 -2

若 x 为偶数， t_x=x+1 ，异或后变大成 x+1

那原先 x+1 的版本中这个点的键值为 -1 ，权值变大后要成为 1

所以将 x+1 的版本中这个点的子树内所有点的 f 值 +2

这同样可用标记永久化实现。

\text{Step 5}

预处理时间复杂度为 O(n\log n)

更改点权的时间复杂度单次为 O(\log n)

查询要套个二分，单次 O(\log^2 n)

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,nn,x,y,opt,tot,tt,l,L,R,mid,cnt,qx,qy;
int a[N],b[N],rt[N],ii[N];
int dfn[N],rev[N],sz[N],dep[N],f[N][20];
int to[N],nextn[N],h[N],edg;char ch;
inline void add(int x,int y){to[++edg]=y,nextn[edg]=h[x],h[x]=edg;}
#define id(x) lower_bound(b+1,b+nn+1,x)-b
struct tree{int l,r,tag,mx;}t[N<<5];
inline void read(int &x){
    x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();
    while(ch>47&&ch<58)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
void write(int x){if(x>9)write(x/10);putchar(48+x%10);}
void build(int &k,int l,int r){
    k=++tot;
    if(l^r){
        int mid=(l+r)>>1;
        build(t[k].l,l,mid);build(t[k].r,mid+1,r);
        t[k].mx=max(t[t[k].l].mx,t[t[k].r].mx);
    }
    else t[k].mx=dep[rev[l]];
}
void update(int &k,int kk,int l,int r,int x,int y,int v){
    k=++tot;t[k]=t[kk];
    if(x<=l&r<=y)t[k].tag+=v,t[k].mx+=v;
    else {
        int mid=(l+r)>>1;
        if(x<=mid)update(t[k].l,t[kk].l,l,mid,x,y,v);
        if(mid<y)update(t[k].r,t[kk].r,mid+1,r,x,y,v);
        t[k].mx=max(t[t[k].l].mx,t[t[k].r].mx)+t[k].tag;
    }
}
int inquiry(int k,int l,int r,int pos){
    if(l^r){
        int mid=(l+r)>>1;
        if(pos<=mid)return inquiry(t[k].l,l,mid,pos)+t[k].tag;
        else return inquiry(t[k].r,mid+1,r,pos)+t[k].tag;
    }
    else return t[k].mx;
}
int inquiry_mx(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y)return t[k].mx;
    int mid=(l+r)>>1;
    if(x<=mid&&mid<y)
        return max(inquiry_mx(t[k].l,l,mid,x,y),inquiry_mx(t[k].r,mid+1,r,x,y))+t[k].tag;
    else if(x<=mid)return inquiry_mx(t[k].l,l,mid,x,y)+t[k].tag;
    else return inquiry_mx(t[k].r,mid+1,r,x,y)+t[k].tag;
}
void init(int x,int anc){
    int i,y;rev[dfn[x]=++tt]=x;
    sz[x]=1;dep[x]=dep[anc]+1;f[x][0]=anc;
    for(i=1;i^20;++i)f[x][i]=f[f[x][i-1]][i-1];
    for(i=h[x];y=to[i],i;i=nextn[i])if(y^anc)init(y,x),sz[x]+=sz[y];
    h[x]=0;
}
int lca(int x,int y){
    int i;if(dep[x]<dep[y])x^=y^=x^=y;
    for(i=19;~i;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(i=19;~i;--i)if(f[x][i]^f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
main(){
    read(n);read(m);register int i,j;
    for(i=1;i<=n;++i){read(a[i]),b[++nn]=a[i];if(a[i]^1)b[++nn]=a[i]^1;}
    sort(b+1,b+nn+1);nn=unique(b+1,b+nn+1)-b-1;
    for(i=1;i^n;++i)read(x),read(y),add(x,y),add(y,x);
    init(1,0);edg=0;build(rt[0],1,n);
    for(i=1;i<=n;++i)add(ii[i]=id(a[i]),i),ii[i]+=(a[i]&1)^1;
    for(i=1;rt[i]=rt[i-1],i<=nn;++i)for(j=h[i-1];x=to[j],j;j=nextn[j])
        update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,-2);
    while(m--){
        read(opt);read(x);
        if(opt==1){
            i=ii[x];
            if(a[x]&1)update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,-2);
            else update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,2);
            a[x]^=1;
        }
        else {
            read(y);l=lca(x,y);
            L=0;R=nn;
            while(L<R){
                mid=L+R+1>>1;cnt=0;
                cnt+=inquiry_mx(rt[mid],1,n,dfn[x],dfn[x]+sz[x]-1);
                cnt+=inquiry_mx(rt[mid],1,n,dfn[y],dfn[y]+sz[y]-1);
                cnt-=(inquiry(rt[mid],1,n,dfn[l])<<1)+(a[l]>=b[mid]?-1:1);
                if(cnt>=0)L=mid;else R=mid-1;
            }
            write(b[L]);putchar('\n');
        }
    }
}