P3899 [湖南集训]更为厉害（线段树合并、长链剖分、二维数点）

P3899 [湖南集训]更为厉害（线段树合并、长链剖分、二维数点） P3899 [湖南集训]更为厉害

• 若 deep b < deep a text{deep}_b
• 若 deep b > deep a text{deep}_b>text{deep}_a deepb​>deepa​：c 在点 b 的子树中，所以此时每个点 b 的贡献为 sz b − 1 text{sz}_b−1 szb​−1

对于上述条件，满足深度限制即可。

Code1

线段树合并暴力合并子树

1.80s / 90.65MB / 1.82KB C++17

#include

using namespace std;
using ll=long long;
constexpr int N=300010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int n,q;
struct node
{
    int l,r;
    ll v;
}tree[N*40];
int root[N],cnt;
void insert(int &u,int l,int r,int pos,ll v)
{
    if(!u) u=++cnt;
    if(l==r) return tree[u].v+=v,void();
    
    int mid=l+r>>1;
    if(pos<=mid) 
        insert(tree[u].l,l,mid,pos,v);
    else
        insert(tree[u].r,mid+1,r,pos,v);
    
    tree[u].v=tree[tree[u].l].v+tree[tree[u].r].v;
}
ll query(int u,int l,int r,int L,int R)
{
    if(!u) return 0ll;
    if(L<=l&&r<=R) return tree[u].v;
    int mid=l+r>>1;
    ll v=0;
    if(L<=mid)
        v+=query(tree[u].l,l,mid,L,R);
    if(R>mid)
        v+=query(tree[u].r,mid+1,r,L,R);
    return v;
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    int u=++cnt;
    tree[u].v=tree[x].v+tree[y].v;
    tree[u].l=merge(tree[x].l,tree[y].l);
    tree[u].r=merge(tree[x].r,tree[y].r);
    return u;
}

int dep[N],sz[N];

void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    sz[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        root[u]=merge(root[u],root[v]);
    }
    insert(root[u],1,n,dep[u],sz[u]-1);
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    
    cin>>n>>q;
    memset(h,-1,sizeof h);
    for(int i=1;i>u>>v;
        add(u,v),add(v,u);
    }
    dfs(1,0);
    while(q--)
    {
        int p,k;
        cin>>p>>k;
        ll ans=0;
        ans+=1ll*min(k,dep[p]-1)*(sz[p]-1);
        ans+=query(root[p],1,n,dep[p]+1,dep[p]+k);
        cout< 
Code2 
长链剖分
 
1.51s / 48.94MB / 1.60KB C++17
 
#include

using namespace std;
using ll=long long;
constexpr int N=300010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
ll ans[N];
int n,m;
int ht[N],son[N],sz[N],dep[N];
void dfs1(int u,int fa)
{
    sz[u]=1;
    dep[u]=dep[fa]+1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(ht[son[u]]> q[N];
void dfs2(int u,int fa)
{
    if(son[u])
    {
        f[son[u]]=f[u]+1;
        dfs2(son[u],u);
        tag[u]=tag[son[u]]+sz[son[u]]-1;
        
    }
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa||v==son[u]) continue;
        
        f[v]=now;now+=ht[v];
        dfs2(v,u);
        tag[u]+=tag[v]+sz[v]-1;
        for(int j=1;j>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i>u>>v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int p,k;
        cin>>p>>k;
        q[p].push_back({k,i});
    }
    dfs1(1,0);
    f[1]=now;now+=ht[1];
    dfs2(1,0);
    for(int i=1;i<=m;i++) cout< 
Code3 
主席树二维数点
 
2.58s / 107.27MB / 1.85KB C++17
 
#include

using namespace std;
using ll=long long;
constexpr int N=300010;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int n,q;
struct node
{
    int l,r;
    ll v;
}tree[N*40];
int rt[N],cnt;
void insert(int &u,int o,int l,int r,int pos,ll v)
{
    tree[u=++cnt]=tree[o];
    tree[u].v+=v;
    if(l==r) return;
    
    int mid=l+r>>1;
    if(pos<=mid) 
        insert(tree[u].l,tree[o].l,l,mid,pos,v);
    else
        insert(tree[u].r,tree[o].r,mid+1,r,pos,v);
}
ll query(int u,int l,int r,int L,int R)
{
    if(!u) return 0ll;
    if(L<=l&&r<=R) return tree[u].v;
    int mid=l+r>>1;
    ll v=0;
    if(L<=mid)
        v+=query(tree[u].l,l,mid,L,R);
    if(R>mid)
        v+=query(tree[u].r,mid+1,r,L,R);
    return v;
}

int dep[N],sz[N];
int L[N],timestamp,R[N];

void dfs1(int u,int fa)
{
    L[u]=++timestamp;
    
    dep[u]=dep[fa]+1;
    sz[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
    R[u]=timestamp;
    
}
void dfs2(int u,int fa)
{
    insert(rt[L[u]],rt[L[u]-1],1,n,dep[u],sz[u]-1);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int v=e[i];
        if(v==fa) continue;
        dfs2(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    
    cin>>n>>q;
    memset(h,-1,sizeof h);
    for(int i=1;i>u>>v;
        add(u,v),add(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);

    while(q--)
    {
        int u,k;
        cin>>u>>k;
        ll ans=0;
        ans+=1ll*min(k,dep[u]-1)*(sz[u]-1);
        ans+=query(rt[R[u]],1,n,dep[u]+1,dep[u]+k)-query(rt[L[u]-1],1,n,dep[u]+1,dep[u]+k);
        
        cout< 
 
本质上线段树合并是通过该节点的子树构建当前树直接得到子树信息，而主席树是通过转化dfs序构建前缀树，通过作差得到子树的信息。
 
如果某些信息不支持做差得到，那么主席树的做法将失效，而线段树合并仍然适用
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4751709.html