LibreOJ 2107 「JLOI2015」城池攻占

注意到牺牲了就不会再有贡献，考虑维护一个小根堆，然后每次从儿子合并之后一直弹直到堆顶不小于防御值。

发现还要整体标记，左偏树能够比较容易地实现标记，当然也可以不下推维护整体标记，只不过有除法的话可能有精度问题。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x,1);
}

const int N = 3e5;
int n,m,a[N + 5],w[N + 5],c[N + 5],ans[N + 5];
int fa[N + 5],dep[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
long long h[N + 5],v[N + 5],s[N + 5];
struct node
{
    int dis,fa,id;
    int ls,rs;
    long long val,add,mul;
} tree[N + 5];
int rt[N + 5],st[N + 5],top;
inline int new_node(int x,long long v)
{
    static int tot = 0;
    int p = top ? st[top--] : ++tot;
    tree[p].val = v,tree[p].id = x,tree[p].dis = tree[p].ls = tree[p].rs = tree[p].add = tree[p].fa = 0,tree[p].mul = 1;
    return p;
}
inline void push(int p)
{
    if(tree[p].mul ^ 1)
    {
        tree[tree[p].ls].mul *= tree[p].mul,tree[tree[p].ls].add *= tree[p].mul,tree[tree[p].ls].val *= tree[p].mul;
        tree[tree[p].rs].mul *= tree[p].mul,tree[tree[p].rs].add *= tree[p].mul,tree[tree[p].rs].val *= tree[p].mul;
        tree[p].mul = 1;
    }
    if(tree[p].add)
    {
        tree[tree[p].ls].add += tree[p].add,tree[tree[p].ls].val += tree[p].add;
        tree[tree[p].rs].add += tree[p].add,tree[tree[p].rs].val += tree[p].add;
        tree[p].add = 0;
    }
}
inline void update_add(int p,long long k)
{
    p && (tree[p].add += k,tree[p].val += k);
}
inline void update_mul(int p,long long k)
{
    p && (tree[p].mul *= k,tree[p].add *= k,tree[p].val *= k);
}
int merge(int p,int q)
{
    if(!p || !q)
        return p | q;
    if(tree[p].val > tree[q].val)
        swap(p,q);
    push(p),push(q);
    tree[tree[p].rs = merge(tree[p].rs,q)].fa = p;
    if(tree[tree[p].ls].dis < tree[tree[p].rs].dis)
        swap(tree[p].ls,tree[p].rs);
    tree[p].dis = tree[tree[p].rs].dis + 1;
    return p;
}
inline void pop(int &p)
{
    push(p),st[++top] = p,tree[p = merge(tree[p].ls,tree[p].rs)].fa = 0;
}
void dfs(int p)
{
    for(register int i = first[p];i;i = pre[i])
        dep[to[i]] = dep[p] + 1,dfs(to[i]),rt[p] = merge(rt[p],rt[to[i]]);
    for(;rt[p] && tree[rt[p]].val < h[p];w[tree[rt[p]].id] = p,++ans[p],pop(rt[p]));
    a[p] ? update_mul(rt[p],v[p]) : update_add(rt[p],v[p]);
}
int main()
{
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(h[i]);
    for(register int i = 2;i <= n;++i)
        read(fa[i]),read(a[i]),read(v[i]),add(fa[i],i);
    for(register int i = 1;i <= m;++i)
        read(s[i]),read(c[i]),rt[c[i]] = merge(rt[c[i]],new_node(i,s[i]));
    dep[1] = 1,dfs(1);
    for(register int i = 1;i <= n;++i)
        printf("%d\n",ans[i]);
    for(register int i = 1;i <= m;++i)
        printf("%d\n",dep[c[i]] - dep[w[i]]);
}