【JLOI2015】bzoj4003 城池攻占

要求的東西那麼多，很顯然需要模拟整個過程。不難發現可并堆很好維護，而且也支援打标記。

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=;
LL rd()
{
    LL x=,f=;
    char c=getchar();
    while (c<'0'||c>'9')
    {
        if (c=='-') f=;
        c=getchar();
    }
    while (c>='0'&&c<='9')
    {
        x=x*+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
int root[maxn],lson[maxn],rson[maxn],height[maxn],pass[maxn],
f[maxn],a[maxn],c[maxn],num[maxn],pos[maxn],du[maxn],que[maxn],
n,m;
LL h[maxn],v[maxn],s[maxn],plus[maxn],mul[maxn],val[maxn];
void down(int u)
{
    if (!u) return;
    if (mul[u]>)
    {
        val[u]*=mul[u];
        if (lson[u])
        {
            plus[lson[u]]*=mul[u];
            mul[lson[u]]*=mul[u];
        }
        if (rson[u])
        {
            plus[rson[u]]*=mul[u];
            mul[rson[u]]*=mul[u];
        }
        mul[u]=;
    }
    if (plus[u])
    {
        val[u]+=plus[u];
        if (lson[u]) plus[lson[u]]+=plus[u];
        if (rson[u]) plus[rson[u]]+=plus[u];
        plus[u]=;
    }
    if (pass[u])
    {
        pos[u]+=pass[u];
        if (lson[u]) pass[lson[u]]+=pass[u];
        if (rson[u]) pass[rson[u]]+=pass[u];
        pass[u]=;
    }
}
void dfs(int u)
{
    if (!u) return;
    down(u);
    dfs(lson[u]);
    dfs(rson[u]);
}
int merge(int u,int v)
{
    down(u);
    down(v);
    if (u*v==) return u+v;
    if (val[u]>val[v]) swap(u,v);
    rson[u]=merge(rson[u],v);
    if (height[rson[u]]>height[lson[u]]) swap(rson[u],lson[u]);
    height[u]=height[rson[u]]+;
    return u;
}
int main()
{
    int hd=,tl=,x;
    n=rd();
    m=rd();
    for (int i=;i<=n;i++) h[i]=rd();
    for (int i=;i<=n;i++)
    {
        f[i]=rd();
        a[i]=rd();
        v[i]=rd();
        du[f[i]]++;
    }
    for (int i=;i<=m;i++)
    {
        val[i]=rd();
        s[i]=rd();
        plus[i]=;
        mul[i]=;
        height[i]=;
        root[s[i]]=merge(root[s[i]],i);
    }
    for (int i=;i<=n;i++)
        if (!du[i]) que[++tl]=i;
    while (hd<=tl)
    {
        x=que[hd++];
        while (root[x])
        {
            down(root[x]);
            if (val[root[x]]<h[x])
            {
                num[x]++;
                root[x]=merge(lson[root[x]],rson[root[x]]);
            }
            else break;
        }
        pass[root[x]]++;
        if (a[x]) mul[root[x]]*=v[x];
        else plus[root[x]]+=v[x];
        if (x>)
        {
            root[f[x]]=merge(root[f[x]],root[x]);
            du[f[x]]--;
            if (!du[f[x]]) que[++tl]=f[x];
        }
    }
    dfs(root[]);
    for (int i=;i<=n;i++) printf("%d\n",num[i]);
    for (int i=;i<=m;i++) printf("%d\n",pos[i]);
}