http://www.lydsy.com/JudgeOnline/problem.php?id=4003
可合并堆。
每个点都有一个小根堆，记住可以到这个点的骑士有哪些，以战斗力为关键字。
从底层到顶层不断合并，然后不断取出战斗力的最小值，如果小于防御值，则去掉最小值。
操作可以打标记。
我用了左偏树。
左偏树太不熟悉了，打错了2个地方，去了皮的大土豆~OTATO
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL;
typedef double DB;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b) for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=; int N,M;
vector<int> son[maxN+];
vector<int> Q[maxN+];
int f[maxN+],dep[maxN+],a[maxN+];
LL h[maxN+],v[maxN+];
int c[maxN+];
LL s[maxN+]; struct Tnode
{
Tnode *l,*r;
LL v,mu,add;int id,dis;
inline Tnode(LL _v=,LL _mu=,LL _add=,int _id=,int _dis=){l=;r=;v=_v;mu=_mu;add=_add;id=_id;dis=_dis;}
inline int ldis(){return l?l->dis:;}
inline int rdis(){return r?r->dis:;}
inline void down()
{
if(mu== && add==)return;
if(l)l->v=l->v*mu+add,l->add=mu*l->add+add,l->mu=mu*l->mu;
if(r)r->v=r->v*mu+add,r->add=mu*r->add+add,r->mu=mu*r->mu;
mu=;add=;
}
}; inline Tnode *uni(Tnode *a,Tnode *b)
{
if(!a)return b;
if(!b)return a;
a->down();
b->down();
if(a->v > b->v)swap(a,b);
a->r=uni(a->r,b);
if(a->ldis() < a->rdis())swap(a->l,a->r);
a->dis=a->rdis()+;
return a;
} Tnode mem[maxN+];
Tnode *rt[maxN+]; int ge[maxN+],out[maxN+]; int main()
{
/*freopen("bzoj4003.in","r",stdin);
freopen("bzoj4003.out","w",stdout);*/
int i,j;
N=gint();M=gint();
re(i,,N)h[i]=gll();
re(i,,N)f[i]=gll(),a[i]=gint(),v[i]=gll(),son[f[i]].p_b(i);
re(i,,M)s[i]=gll(),c[i]=gint(),Q[c[i]].p_b(i);
re(i,,N)dep[i]=dep[f[i]]+;
re(i,,M)mem[i]=Tnode(s[i],,,i,);
red(i,N,)
{
re(j,,int(son[i].size())-)
{
int ch=son[i][j];
rt[i]=uni(rt[i],rt[ch]);
}
re(j,,int(Q[i].size())-)
{
int t=Q[i][j];
rt[i]=uni(rt[i],&mem[t]);
}
while(rt[i] && rt[i]->v<h[i])
{
ge[i]++;
int t=rt[i]->id;
out[t]=dep[c[t]]-dep[i];
rt[i]->down();////////////////////////////////////////////注意这里要down
rt[i]=uni(rt[i]->l,rt[i]->r);
}
if(rt[i])
if(a[i]==)
rt[i]->v+=v[i],rt[i]->add+=v[i];
else
rt[i]->v*=v[i],rt[i]->mu*=v[i],rt[i]->add*=v[i];
}
while(rt[])
{
int t=rt[]->id;
out[t]=dep[c[t]];
rt[]->down();////////////////////////////////////////////注意这里要down
rt[]=uni(rt[]->l,rt[]->r);
}
re(i,,N)PF("%d\n",ge[i]);
re(i,,M)PF("%d\n",out[i]);
return ;
}
然后有另外一种不适用这题的方法。
我们发现，如果某个骑士的初始战斗力为x，那么骑士在当前点的战斗力为ax+b，其实a和b只跟出发点和当前点的位置有关，与x无关。
并且我们发现a一定是正数。
类似于LCA，
to[i][j]表示i号点跳2^j次到的点。
jump[i][j]表示，这是一个pair，表示一个初始位置在i号点的骑士的初始战斗力为x，跳2^j次后，战斗力变成jump[i][j].fi*x+jump[i][j].se，其实jump[i][j].fi和jump[i][j].se只和i，有关，与x无关。
minx[i][j]表示，一个初始位置在i号点的骑士的初始战斗力为x，想要跳2^j次，x至少要为minx[i][j]。
容易发现x[i][j]随着j的递增而递增，有单调性。
可以用nlogn的时间求出。
然后对于初始位置在i的骑士，记其初始战斗力为x，二分j，判断x与minx[i][j]的大小关系即可。
但是这道题不适用的地方在于：
（1）MLE
（2）题目保证“任何时候骑士战斗力值的绝对值不超过 10^18”，不是"骑士跑到到根战斗力值的绝对值不超过 10^18“，这样很容易就爆longlong了。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL;
typedef double DB;
typedef pair<LL,LL> PLL;
typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b) for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define SF scanf
#define PF printf
#define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} const DB EPS=1e-;
inline int sgn(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}
const DB Pi=acos(-1.0); inline int gint()
{
int res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
}
inline LL gll()
{
LL res=;bool neg=;char z;
for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());
if(z==EOF)return ;
if(z=='-'){neg=;z=getchar();}
for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());
return (neg)?-res:res;
} const int maxN=;
const LL INF=(1LL<<)-; int N,M;
LL s[maxN+];int c[maxN+];
int f[maxN+],a[maxN+];
LL h[maxN+],v[maxN+]; int dep[maxN+];
int to[maxN+][];
PLL jump[maxN+][];
LL minx[maxN+][]; int g[maxN+],out[maxN+]; int main()
{
freopen("bzoj4003.in","r",stdin);
freopen("bzoj4003.out","w",stdout);
int i,j;
N=gint();M=gint();
re(i,,N)h[i]=gll();
re(i,,N)f[i]=gint(),a[i]=gint(),v[i]=gll();
re(i,,M)s[i]=gll(),c[i]=gint(); dep[]=;
re(j,,)to[][j]=;
re(j,,)jump[][j]=PLL(,);
re(j,,)minx[][j]=INF;
re(i,,N)
{
dep[i]=dep[f[i]]+;
to[i][]=f[i];
re(j,,)to[i][j]=to[to[i][j-]][j-];
if(a[i]==) jump[i][]=PLL(,v[i]); else jump[i][]=PLL(v[i],);
re(j,,)
{
LL da=jump[i][j-].fi,db=jump[i][j-].se,a=jump[to[i][j-]][j-].fi,b=jump[to[i][j-]][j-].se;
jump[i][j]=PLL(a*da,a*db+b);
}
minx[i][]=h[i];
re(j,,)
{
minx[i][j]=minx[i][j-];
LL a=jump[i][j-].fi,b=jump[i][j-].se,temp=minx[to[i][j-]][j-];
if(temp==INF) upmax(minx[i][j],INF); else upmax(minx[i][j],(temp-b-)/a+);
}
} re(i,,M)
{
int p=c[i];LL x=s[i];
red(j,,)
if(x>=minx[p][j])
{
x=x*jump[p][j].fi+jump[p][j].se;
p=to[p][j];
}
if(x<h[p])g[p]++;
out[i]=dep[c[i]]-dep[p];if(x>=h[p])out[i]++;
} re(i,,N)PF("%d\n",g[i]);
re(i,,M)PF("%d\n",out[i]); return ;
}