坑 -1

Problem

小铭铭最近获得了一副新的桌游，游戏中需要用 m 个骑士攻占 n 个城池。这 n 个城池用 1 到 n 的整数表示。除 1 号城池外，城池 i 会受到另一座城池 fi 的管辖，其中 fi <i。也就是说，所有城池构成了一棵有根树。这 m 个骑士用 1 到 m 的整数表示，其中第 i 个骑士的初始战斗力为 si，第一个攻击的城池为 ci。

每个城池有一个防御值 hi，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 1 号城池，或牺牲为止。

除 1 号城池外，每个城池 i 会给出一个战斗力变化参数 ai;vi。若 ai =0，攻占城池 i 以后骑士战斗力会增加 vi；若 ai =1，攻占城池 i 以后，战斗力会乘以 vi。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

Solution

可并堆从下往上模拟
然后打个 lazy 标记就行
记得下放

Code

// Code by ajcxsu
// Problem: cities' defender

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0;
    x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl?-1:1;
}

const int N=3e5+10, M=6e5+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int mo[N]; ll v[N];

struct Node* nil;
struct Node {
    Node *ls, *rs;
    ll v, t1=0, t2=1;
    int id;
    void pud() {
        if(!t1 && t2==1) return;
        ls->t1*=t2, ls->t2*=t2, ls->t1+=t1;
        rs->t1*=t2, rs->t2*=t2, rs->t1+=t1;
        v=v*t2+t1;
        t1=0, t2=1;
    }
} po[N];
void ini() {
    nil=po, nil->ls=nil->rs=nil, nil->v=0;
}
Node *merge(Node *a, Node *b) {
    if(a==nil) return b;
    if(b==nil) return a;
    a->pud(), b->pud();
    if(a->v<b->v) swap(a, b);
    a->rs=b->ls, b->ls=a;
    return b;
}
Node *merges(Node *x) {
    if(x->rs==nil) return x;
    Node *y=x->rs, *z=y->rs;
    x->pud(), y->pud();
    x->rs=y->rs=nil;
    return merge(merge(x, y), merges(z));
}
Node *top(Node *x) {
    x->pud();
    return x;
}
Node *pop(Node *x) {
    x->pud();
    return merges(x->ls);
}

vector<Node*> kni[N];
ll def[N];

int dea[N], vic[N], dep[N], beg[N];
void dfs(int x, int k) {
    dep[x]=k;
    for(int u=h[x];u;u=nexp[u])
        dfs(to[u], k+1);
}
Node *dfs2(int x, Node *nd=nil) {
    int len=kni[x].size();
    for(int i=0;i<len;i++) nd=merge(kni[x][i], nd);
    for(int u=h[x];u;u=nexp[u]) nd=merge(nd, dfs2(to[u]));
    while(nd!=nil && top(nd)->v<def[x]) dea[x]++, vic[top(nd)->id]=dep[x], nd=pop(nd);
    if(!mo[x]) nd->t1+=v[x];
    else nd->t1*=v[x], nd->t2*=v[x];
    return nd;
}

int main() {
    ios::sync_with_stdio(false), ini();
    int n, m;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) gn(def[i]);
    int fa;
    for(int i=2;i<=n;i++) gn(fa), gn(mo[i]), gn(v[i]), ins(fa, i);
    ll u, v;
    Node *nd;
    dfs(1, 1);
    for(int i=1;i<=m;i++) {
        gn(u), gn(v), nd=po+i, *nd=*nil, nd->v=u, nd->id=i, beg[i]=dep[v];
        kni[v].push_back(nd);
    }
    dfs2(1);
    for(int i=1;i<=n;i++) printf("%d\n", dea[i]);
    for(int i=1;i<=m;i++) printf("%d\n", beg[i]-vic[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3261.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆