[JLOI2015]城池攻占——启发式合并

· · 题解

优先队列启发式合并

STL大法好

作为一个蒟蒻，自然是不会左偏树这种东西的，于是就用 c++ 自带的 priority_queue 水过去了。

首先每个节点都开一个优先队列，记录每个节点的队列是哪一个(rt 数组)。这样的话，启发式合并的时候，如果 size 不满足要求，直接交换 rt 的值就行了。

然后同样的，开两个标记数组 Mul,Add 。

那么标记怎么下放呢？

我们不下放！

每个标记就跟着它的优先队列一直跟下去！

具体实现方法：

在 merge 的时候，我们要把 r2 插到 r1 里面，就可以计算出来 r2 中每个元素的值 x。为了去适应 r1 的标记，就把 (x-Add[r1])/Mul[r1] 这个值插到 r1 里面就行了。

因为要有除法，所以优先队列要开long \;double类型的（double 只有80分）

还有个细节就是 get 函数，是四舍五入用的，这样对精度有很大帮助（或许吧）。

因为是启发式合并，每个节点最多被插入 log 次，每次是 log 的，所以总时间复杂度:O(nlog^2n)。

由于达不到上界，跑的还是很快的，只用了 600ms

#include<bits/stdc++.h>
#define N 300005
#define int long long
#define double long double
using namespace std;

inline void rd(int &X){
    X=0;int w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=w?-X:X;
}

int n,m;
int head[N],cnt;
int rt[N],Add[N],Mul[N];
int h[N],fa[N],a[N],v[N];
int fx[N],ex[N],d[N],ans[N];
struct pr{double val;int id;};
struct nd{int nxt,to;}e[N];
priority_queue<pr> q[N];
#define For(x) for(int y,i=head[x];(y=e[i].to);i=e[i].nxt)

bool operator < (pr a,pr b){
    return a.val>b.val;
}
inline void add(int x,int y){
    e[++cnt]=(nd){head[x],y};head[x]=cnt;d[y]=d[x]+1;
}
int get(double x){
    return x-(int)x<0.5 ? (int)x : (int)x+1;
}
int merge(int r1,int r2){
    if(q[r1].size()<q[r2].size()) swap(r1,r2);
    while(q[r2].size()){
        int now=get(q[r2].top().val*Mul[r2]+Add[r2]);
        int ID=q[r2].top().id; q[r2].pop();
        q[r1].push((pr){(double)(now-Add[r1])/Mul[r1],ID});
    }
    return r1;
}
void dfs(int x){

    For(x) dfs(y),rt[x]=merge(rt[x],rt[y]);
    while(q[rt[x]].size()){
        int now=get(q[rt[x]].top().val*Mul[rt[x]]+Add[rt[x]]),ID=q[rt[x]].top().id;
        if(now<h[x]) q[rt[x]].pop(),ex[ID]=x;
        else break;
    }
    if(!a[x]) Add[rt[x]]+=v[x];
    else Mul[rt[x]]*=v[x],Add[rt[x]]*=v[x];
}
signed main(){
    rd(n);rd(m);d[1]=1;
    for(int i=1;i<=n;i++) 
        rd(h[i]),rt[i]=i,Mul[i]=1;
    for(int i=2;i<=n;i++)
        rd(fa[i]),rd(a[i]),rd(v[i]),add(fa[i],i);
    for(int v,i=1;i<=m;i++)
        rd(v),rd(fx[i]),q[fx[i]].push((pr){v,i});
    dfs(1);
    for(int i=1;i<=m;i++)
        ans[ex[i]]++;
    for(int i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
    for(int i=1;i<=m;i++)
        printf("%lld\n",d[fx[i]]-d[ex[i]]);
}

如果此篇题解帮助到你了，记得点赞哦！⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄