大力左偏树向上合并骑士
然后阵亡的骑士就踢堆顶
要处理的就是区间加和减
没开LL见祖宗调了一晚上
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> using namespace std; typedef long long LL; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } LL LLread() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void write(int x) { if(x<0){putchar('-');x=-x;} if(x>=10)write(x/10); putchar(x%10+'0'); } //------------------------------------------------------------------------------------ struct node { int x,y,next; }a[310000];int len,last[310000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } //------------------------------------------------------------------------------------ struct heap { int lc,rc,dep;LL d; LL add,mul; heap(){lc=0,rc=0,dep=1,add=0,mul=1;} }h[310000];int hlen,rt[310000]; void update(int x) { int lc=h[x].lc,rc=h[x].rc; LL add=h[x].add,mul=h[x].mul; h[x].add=0,h[x].mul=1; h[lc].d*=mul,h[lc].d+=add; h[rc].d*=mul,h[rc].d+=add; h[lc].mul*=mul,h[lc].add*=mul,h[lc].add+=add; h[rc].mul*=mul,h[rc].add*=mul,h[rc].add+=add; } int merge(int x,int y) { if(x==0||y==0)return x+y; if(h[x].d>h[y].d)swap(x,y); update(x); h[x].rc=merge(h[x].rc,y); if(h[h[x].lc].dep<h[h[x].rc].dep)swap(h[x].lc,h[x].rc); h[x].dep=h[h[x].lc].dep+1; return x; } int pop(int x) { update(x); return merge(h[x].lc,h[x].rc); } //------------------------------------------------------------------------------------ void baoli(int x,int op,LL vl) { if(op==0)h[x].d+=vl; else h[x].d*=vl; if(h[x].lc!=0)baoli(h[x].lc,op,vl); if(h[x].rc!=0)baoli(h[x].rc,op,vl); } LL df[310000],vl[310000];int op[310000],dep[310000]; LL s[310000];int c[310000];vector<int>vec[310000]; int cas[310000],qas[310000]; void dfs(int x) { for(int i=0;i<vec[x].size();i++)rt[x]=merge(rt[x],vec[x][i]); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; dep[y]=dep[x]+1; dfs(y); rt[x]=merge(rt[x],rt[y]); } //merge while(rt[x]!=0&&h[rt[x]].d<df[x]) { cas[x]++; qas[rt[x]]=dep[c[rt[x]]]-dep[x]; rt[x]=pop(rt[x]); } //del if(rt[x]!=0) { //baoli(rt[x],op[x],vl[x]); if(op[x]==0)h[rt[x]].d+=vl[x],h[rt[x]].add+=vl[x]; else h[rt[x]].d*=vl[x],h[rt[x]].add*=vl[x],h[rt[x]].mul*=vl[x]; } //update } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m,F; n=read(),m=read(); for(int i=1;i<=n;i++)df[i]=LLread(); len=0;memset(last,0,sizeof(last)); for(int i=2;i<=n;i++) F=read(),op[i]=read(),vl[i]=LLread(),ins(F,i); for(int i=1;i<=m;i++) s[i]=LLread(),c[i]=read(),vec[c[i]].push_back(i); hlen=0;h[0].dep=0; memset(rt,0,sizeof(rt)); for(int i=1;i<=m;i++)h[++hlen].d=s[i]; memset(cas,0,sizeof(cas)); memset(qas,-1,sizeof(qas)); dep[1]=1;dfs(1); for(int i=1;i<=m;i++) if(qas[i]==-1)qas[i]=dep[c[i]]; for(int i=1;i<=n;i++)write(cas[i]),puts(""); for(int i=1;i<=m;i++)write(qas[i]),puts(""); return 0; }