「JLOI2015」城池攻占 解题报告

时间:2023-01-12 15:23:20

「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