[BZOJ4003][JLOI2015]城池攻占(左偏树)

这题有多种做法，一种是倍增预处理出每个点往上走2^i步最少需要的初始战斗力，一种是裸的启发式合并带标记splay。

每个点合并能攻占其儿子的所有骑士，删去所有无法攻占这个城市的骑士并记录答案。

注意到splay每次实际上只需要取出最小的元素判断是否牺牲，这显然可以用堆维护。

关于可并堆打标记：和线段树打标记一样，维护乘法标记a和加法标记b，所有元素表示为ax+b，用同样的方法下传。

注意merge前要先push。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 typedef long long ll;

 using namespace std;

 const int N=;

 int n,m,cnt,a[N],fa[N],rt[N],bg[N],ed[N],ls[N],rs[N],dis[N],dep[N],dead[N],to[N],nxt[N],h[N];

 ll mul[N],plu[N],v[N],p[N],d[N];

 void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

 void put(int x,ll a,ll b){

     if (!x) return;

     v[x]=v[x]*a+b; mul[x]*=a; plu[x]=plu[x]*a+b;

 }

 void push(int x){

     put(ls[x],mul[x],plu[x]); put(rs[x],mul[x],plu[x]);

     mul[x]=; plu[x]=;

 }

 int merge(int x,int y){

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

     push(x); push(y);

     if (v[x]>v[y]) swap(x,y);

     rs[x]=merge(rs[x],y);

     if (dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);

     dis[x]=dis[rs[x]]+; return x;

 }

 int pop(int x){ push(x); return merge(ls[x],rs[x]); }

 void dfs(int x,int fa){

     dep[x]=dep[fa]+;

     For(i,x) dfs(k=to[i],x),rt[x]=merge(rt[x],rt[k]);

     while (rt[x] && v[rt[x]]<d[x])

         dead[x]++,ed[rt[x]]=x,rt[x]=pop(rt[x]);

     if (!a[x]) put(rt[x],,p[x]); else put(rt[x],p[x],);

 }

 int main(){

     freopen("bzoj4003.in","r",stdin);

     freopen("bzoj4003.out","w",stdout);

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

     rep(i,,n) scanf("%lld",&d[i]);

     rep(i,,n) scanf("%d%d%lld",&fa[i],&a[i],&p[i]),add(fa[i],i);

     rep(i,,m) mul[i]=,scanf("%lld%d",&v[i],&bg[i]),rt[bg[i]]=merge(rt[bg[i]],i);

     dfs(,);

     rep(i,,n) printf("%d\n",dead[i]);

     rep(i,,m) printf("%d\n",dep[bg[i]]-dep[ed[i]]);

     return ;

 }