左偏树(BZOJ4003)

时间：2022-12-27 07:52:59

左偏树打个标记，没了。

#include <cstdio>

#include <vector>

using namespace std;

typedef long long ll;

const int N = ;

int n,m,e,x,tt,c[N],d[N],a[N],hd[N],nxt[N],to[N],rt[N],f[N],g[N];

ll h[N],v[N],s[N];

vector<int> vc[N];

struct nd {int l,r,d,id; ll w,ad,mu;}t[N];

void add(int x, int y) {to[++e] = y, nxt[e] = hd[x], hd[x] = e;}

void pd(int x) {

    t[t[x].l].mu *= t[x].mu, t[t[x].l].ad *= t[x].mu, t[t[x].l].w *= t[x].mu;

    t[t[x].r].mu *= t[x].mu, t[t[x].r].ad *= t[x].mu, t[t[x].r].w *= t[x].mu;

    t[t[x].l].ad += t[x].ad, t[t[x].r].ad += t[x].ad, t[t[x].l].w += t[x].ad, t[t[x].r].w += t[x].ad;

    t[x].mu = , t[x].ad = ;

}

int mrg(int x, int y) {

    if(!x || !y) return x+y;

    if(t[x].w > t[y].w) swap(x, y);

    pd(x);

    t[x].r = mrg(t[x].r, y);

    if(t[t[x].l].d < t[t[x].r].d) swap(t[x].l, t[x].r);

    t[x].d = t[t[x].r].d+;

    return x;

}

void dfs(int x) {

    for(int i = ; i < vc[x].size(); i++)

        t[++tt].id = vc[x][i], t[tt].w = s[vc[x][i]], t[tt].mu = , rt[x] = mrg(rt[x], tt);

    for(int i = hd[x]; i; i = nxt[i]) d[to[i]] = d[x]+, dfs(to[i]), rt[x] = mrg(rt[x], rt[to[i]]);

    while(rt[x] && t[rt[x]].w < h[x])

        f[x]++, g[t[rt[x]].id] = x, pd(rt[x]), rt[x] = mrg(t[rt[x]].l, t[rt[x]].r);

    if(a[x]) t[rt[x]].mu *= v[x], t[rt[x]].ad *= v[x], t[rt[x]].w *= v[x];

    else t[rt[x]].ad += v[x], t[rt[x]].w += v[x];

}

int main() {

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; i++) scanf("%lld", &h[i]);

    for(int i = ; i <= n; i++) scanf("%d%d%lld", &x, &a[i], &v[i]), add(x, i);

    for(int i = ; i <= m; i++) scanf("%lld%d", &s[i], &c[i]), vc[c[i]].push_back(i);

    d[] = , dfs();

    for(int i = ; i <= n; i++) printf("%d\n", f[i]);

    for(int i = ; i <= m; i++) printf("%d\n", d[c[i]]-d[g[i]]);

    return ;

}

相关文章