专栏文章

题解：P13698 「CyOI」追忆

GGraphcity
P13698题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miodaaqt
此快照首次捕获于
2025/12/02 17:19
3 个月前
此快照最后确认于
2025/12/02 17:19
3 个月前
查看原文
首先把值域离散化，变成 [1,n][1,n]。考虑对值域分块。
对于询问，我们首先需要确认中位数在哪一块。设 fif_i 表示 DD 中有多少个数在块 ii 内，设 cnti,jcnt_{i,j} 表示 ii 到根的链上有多少个点的值在块 jj 内。对于操作 1 就是 fif_i 加上 cntx,i+cnty,i−cntLCA,i−cntfaLCA,icnt_{x,i}+cnt_{y,i}-cnt_{LCA,i}-cnt_{fa_{LCA},i}。对于操作 3 就是全局 ×2\times 2。通过 ff 数组我们就可以 O(n)O(\sqrt n) 定位到中位数所在的块。
然后我们再设 gig_i 表示 DD 中有多少个数字 =i=i。我们需要做的操作有：链加，全局 ×2\times 2，单点查。通过树上差分我们转化成：单点加，全局 ×2\times 2，子树（区间）查。用分块可以做到单次修改 O(n)O(\sqrt n)，单次查询 O(1)O(1)。
定位到中位数所在的块后，在块内从小往大一个一个扫就可以确定中位数。
总时间复杂度 O(nn)O(n\sqrt n)。
CPP
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5,B=400;

int n,m,val[Maxn+5],h[Maxn+5],rk[Maxn+5];
int fa[Maxn+5],dep[Maxn+5],dfn[Maxn+5],siz[Maxn+5],cur;
int st[Maxn+5][20],cnt[Maxn+5][B+5]; ll all[Maxn+5],dxv;
int L[Maxn+5],R[Maxn+5],dx[Maxn+5],tot;
vector<int> v[Maxn+5];

struct DS
{
    ll t[Maxn+5],sum[Maxn+5],tag[Maxn+5],pr[Maxn+5],sp[Maxn+5];
    inline void push_down(int x) {For(i,L[x],R[x]) t[i]*=tag[x]; sum[x]*=tag[x],tag[x]=1;}
    inline void Add(int x,ll k)
    {
        int id=dx[x],l=L[id]; if(tag[id]!=1) push_down(id);
        t[x]+=k,sum[id]+=k; pr[l]=t[l]; For(i,l+1,R[id]) pr[i]=pr[i-1]+t[i];
        For(i,1,tot) sp[i]=sp[i-1]+sum[i]*tag[i];
    }
    inline ll Get(int x)
    {
        if(x==0) return 0ll; int id=dx[x];
        return sp[id-1]+pr[x]*tag[id];
    }
    inline ll Get(int l,int r) {return Get(r)-Get(l-1);}
} D;

inline void dfs(int x,int f)
{
    fa[x]=f,dep[x]=dep[f]+1,siz[x]=1,dfn[x]=++cur,st[dfn[x]][0]=f;
    for(auto y:v[x]) if(y!=f) dfs(y,x),siz[x]+=siz[y];
}
inline int GetMin(int x,int y) {return dfn[x]<dfn[y]?x:y;}
inline int LCA(int x,int y)
{
    if(x==y) return x; if((x=dfn[x])>(y=dfn[y])) swap(x,y);
    int len=__lg(y-x++); return GetMin(st[x][len],st[y-(1<<len)+1][len]);
}
inline void dfs2(int x,int f)
{
    memcpy(cnt[x],cnt[f],sizeof(cnt[x])),cnt[x][dx[h[x]]]++;
    for(auto y:v[x]) if(y!=f) dfs2(y,x);
}
inline void Init()
{
    cin>>n; For(i,1,n) cin>>val[i];
    iota(rk+1,rk+n+1,1);
    sort(rk+1,rk+n+1,[&](int a,int b){return val[a]<val[b];});
    For(i,1,n) h[rk[i]]=i;
    For(i,1,n-1)
    {
        int a,b; cin>>a>>b;
        v[a].push_back(b),v[b].push_back(a);
    }
    dfs(1,0); For(j,1,19) for(int i=1;i+(1<<j)-1<=n;++i)
        st[i][j]=GetMin(st[i][j-1],st[i+(1<<j-1)][j-1]);
    cin>>m;
    for(int i=1;i<=n;i+=B)
    {
        ++tot,L[tot]=i,R[tot]=min(i+B-1,n);
        For(j,L[tot],R[tot]) dx[j]=tot;
    }
    dfs2(1,0);
    For(i,1,tot) D.tag[i]=1;
}
inline void Modify(int x,int y,int k)
{
    int z=LCA(x,y);
    D.Add(dfn[x],k),D.Add(dfn[y],k),D.Add(dfn[z],-k);
    if(fa[z]) D.Add(dfn[fa[z]],-k);
    For(i,1,tot)
    {
        int res=cnt[x][i]+cnt[y][i]-cnt[z][i]-cnt[fa[z]][i];
        all[i]+=1ll*res*k;
    } dxv+=1ll*k*(dep[x]+dep[y]-2*dep[z]+1);
}
inline ll Get(int x) {return D.Get(dfn[x],dfn[x]+siz[x]-1);}
inline int Count()
{
    ll px=(dxv+1)/2; int id=0;
    For(i,1,tot) {if(px>all[i]) px-=all[i]; else {id=i; break;}}
    For(i,L[id],R[id])
    {
        ll res=Get(rk[i]);
        if(px>res) px-=res; else return i;
    } return 0;
}

int main()
{
    Init();
    while(m--)
    {
        int op,x,y,k; cin>>op;
        if(op==1) {cin>>x>>y>>k; Modify(x,y,k);}
        if(op==2) {printf("%d\n",val[rk[Count()]]);}
        if(op==3)
        {
            For(i,1,tot) D.tag[i]*=2,D.sp[i]*=2;
            For(i,1,tot) all[i]*=2; dxv*=2;
        }
    }
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...