「JLOI2015」城池攻占

注意到任意两个人的战斗力相对大小的不变的

可以离线的把所有人赛到初始点的堆里

然后做启发式合并就可以了

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

#define ll long long

const int N=3e5+10;

template <class T>

void read(T &x)

{

	int f=0;x=0;char c=getchar();

	while(!isdigit(c)) f|=c=='-',c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	x=f?-x:x;

}

int head[N],to[N],Next[N],cnt;

void add(int u,int v)

{

	to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int n,m,op[N],ans1[N],ans2[N],st[N],dep[N];

ll h[N],a[N];

struct node

{

	ll mul,add;

	node(){}

	node(ll Mul,ll Add){mul=Mul,add=Add;}

}tag[N];

#define ls ch[x][0]

#define rs ch[x][1]

int ch[N][2],dis[N],root[N];ll dat[N];

void addtag(int x,node tg)

{

	if(!x) return;

	dat[x]=dat[x]*tg.mul+tg.add;

	tag[x].mul*=tg.mul,tag[x].add*=tg.mul;

	tag[x].add+=tg.add;

}

void pushdown(int x)

{

	if(tag[x].mul==1&&!tag[x].add) return;

	addtag(ls,tag[x]);

	addtag(rs,tag[x]);

	tag[x].mul=1,tag[x].add=0;

}

int Merge(int x,int y)

{

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

	pushdown(x),pushdown(y);

	if(dat[x]>dat[y]) std::swap(x,y);

	rs=Merge(rs,y);

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

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

	return x;

}

void del(int &x){pushdown(x),x=Merge(ls,rs);}

void dfs(int now)

{

	for(int v,i=head[now];i;i=Next[i])

	{

		dep[v=to[i]]=dep[now]+1;

		dfs(v);

		root[now]=Merge(root[now],root[v]);

	}

	while(dat[root[now]]<h[now])

	{

		ans2[root[now]]=dep[st[root[now]]]-dep[now];

		++ans1[now];

		del(root[now]);

	}

	if(op[now]) addtag(root[now],node(a[now],0));

	else addtag(root[now],node(1,a[now]));

}

int main()

{

	read(n),read(m);

	for(int i=1;i<=n;i++) read(h[i]);

	for(int f,i=2;i<=n;i++) read(f),read(op[i]),read(a[i]),add(f,i);

	h[0]=2e18,dat[0]=3e18;

	for(int i=1;i<=m;i++)

	{

		read(dat[i]),read(st[i]);

		dis[i]=1,tag[i]=node(1,0);

		root[st[i]]=Merge(root[st[i]],i);

	}

	dep[1]=1;dfs(1);

	while(dat[root[1]]<h[0])

	{

		ans2[root[1]]=dep[st[root[1]]];

		del(root[1]);

	}

	for(int i=1;i<=n;i++) printf("%d\n",ans1[i]);

	for(int i=1;i<=m;i++) printf("%d\n",ans2[i]);

	return 0;

}

---

2019.2.26