题目的意思描述非常明确，我们很容易想到最暴力的算法——模拟！
不知道O（nm）的模拟能拿到多少分，反正肯定会T飞的。
我们考虑优化一下，因为各个骑士之间是独立的，但是我们的问题是一个一个枚举骑士复杂度过高，我们可以用全局变量来记录一下每一个骑士团的情况。这样的话，我们对于每一个被攻击的城池建立一棵左偏树，维护当前攻占到这个城池的骑士，然后把战斗力小于城池防御力的骑士踢出去即可。
删除的复杂度最多是O（mlogm），建立左偏树最多也是O（mlogm），瓶颈出现在两棵左偏树合并上。因为不同的骑士团攻打到同一个城池的时候，他们之前获得的buff可能是不同的，我们不能把两个骑士团的情况全都计算之后再正常合并，那样又会T的。解决的方法就是像线段树一样打上标记，注意要先乘后加（这个就和线段树模板是一样的了），每次在合并和删除操作的时候都要下放标记。
这样合并就可以了，最后我们记录答案的话，在向下dfs的过程中记录一下每个点的深度，之后就能知道这个骑士一共攻占过几个城池了。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 300005; const int INF = 1000000009; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to; }e[M<<1]; int n,m,c[M],f[M],dead[M],lc[M],rc[M],size[M],dep[M],kill[M],ecnt,head[M],root[M],dis[M]; ll h[M],v[M],s[M],mul[M],add[M],sum[M]; bool ml[M]; void adde(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void cover(int x,ll a,ll b) { if(!x) return; s[x] *= a,s[x] += b; mul[x] *= a,add[x] *= a,add[x] += b; } void pushdown(int x) { cover(lc[x],mul[x],add[x]),cover(rc[x],mul[x],add[x]); mul[x] = 1,add[x] = 0; } int merge(int x,int y) { if(!x || !y) return x | y; pushdown(x),pushdown(y); if(s[x] > s[y]) swap(x,y); rc[x] = merge(rc[x],y); if(dis[lc[x]] < dis[rc[x]]) swap(lc[x],rc[x]); dis[x] = dis[rc[x]] + 1; return x; } int split(int x) { return merge(lc[x],rc[x]); } void dfs(int x,int fa) { dep[x] = dep[fa] + 1; for(int i = head[x];i;i = e[i].next) dfs(e[i].to,x),root[x] = merge(root[x],root[e[i].to]); while(root[x] && s[root[x]] < h[x]) { pushdown(root[x]); kill[x]++,dead[root[x]] = dep[c[root[x]]] - dep[x]; root[x] = split(root[x]); } if(ml[x]) cover(root[x],v[x],0); else cover(root[x],1,v[x]); } int main() { //dis[0] = -1; n = read(),m = read(); rep(i,1,n) h[i] = read(); rep(i,2,n) f[i] = read(),ml[i] = read(),v[i] = read(),adde(f[i],i); rep(i,1,m) s[i] = read(),c[i] = read(),mul[i] = 1,root[c[i]] = merge(root[c[i]],i); dfs(1,0); while(root[1]) pushdown(root[1]),dead[root[1]] = dep[c[root[1]]],root[1] = split(root[1]); rep(i,1,n) printf("%d ",kill[i]); rep(i,1,m) printf("%d ",dead[i]); return 0; }