这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/03 20:49] jxm2001 |
2020-2021:teams:legal_string:jxm2001:左偏树 [2020/10/21 22:53] (当前版本) jxm2001 |
||
---|---|---|---|
行 285: | 行 285: | ||
=== 题解 === | === 题解 === | ||
+ | 考虑 $\text{dfs}$ 遍历城市,左偏树合并子节点士兵信息,每次弹出堆顶所有 $c\lt h$ 的结点,同时更新答案。 | ||
+ | 对于修改操作,类似线段树懒标记处理即可。由于 $a_i=1$ 时保证 $v_i\gt 0$,所有结点的相对大小不改变,所有懒标记处理可以保证正确性。 | ||
+ | |||
+ | 合并操作总复杂度 $(n\log m)$,弹出操作总复杂度 $O(m\log m)$,修改操作总时间复杂度 $O(n)$。于是总时间复杂度 $O((n+m)\log m)$。 | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | const int MAXN=3e5+5; | ||
+ | namespace Left_Heap{ | ||
+ | struct Node{ | ||
+ | LL val,lazy[2]; | ||
+ | int idx,dis,ch[2]; | ||
+ | void set(int id,LL v){ | ||
+ | idx=id,val=v; | ||
+ | lazy[0]=1,lazy[1]=0; | ||
+ | } | ||
+ | bool operator < (const Node &b)const{return val<b.val||(val==b.val&&idx<b.idx);} | ||
+ | }node[MAXN]; | ||
+ | void init(){node[0].dis=-1;} | ||
+ | void push_tag(int k,LL tag1,LL tag2){ | ||
+ | if(!k)return; | ||
+ | node[k].val=node[k].val*tag1+tag2; | ||
+ | node[k].lazy[0]=node[k].lazy[0]*tag1; | ||
+ | node[k].lazy[1]=node[k].lazy[1]*tag1+tag2; | ||
+ | } | ||
+ | void push_down(int k){ | ||
+ | push_tag(node[k].ch[0],node[k].lazy[0],node[k].lazy[1]); | ||
+ | push_tag(node[k].ch[1],node[k].lazy[0],node[k].lazy[1]); | ||
+ | node[k].lazy[0]=1,node[k].lazy[1]=0; | ||
+ | } | ||
+ | void merge(int &k,int k1,int k2){ | ||
+ | if(!k1||!k2)return k=k1|k2,void(); | ||
+ | push_down(k1);push_down(k2); | ||
+ | if(node[k2]<node[k1])swap(k1,k2); | ||
+ | merge(node[k=k1].ch[1],node[k1].ch[1],k2); | ||
+ | if(node[node[k].ch[0]].dis<node[node[k].ch[1]].dis) | ||
+ | swap(node[k].ch[0],node[k].ch[1]); | ||
+ | node[k].dis=node[node[k].ch[1]].dis+1; | ||
+ | } | ||
+ | }; | ||
+ | struct Heap{ | ||
+ | int sz,rt; | ||
+ | pair<int,LL> top(){return make_pair(Left_Heap::node[rt].idx,Left_Heap::node[rt].val);} | ||
+ | void pop(){ | ||
+ | Left_Heap::push_down(rt); | ||
+ | Left_Heap::merge(rt,Left_Heap::node[rt].ch[0],Left_Heap::node[rt].ch[1]); | ||
+ | sz--; | ||
+ | } | ||
+ | void push(int idx,LL v){ | ||
+ | Left_Heap::node[idx].set(idx,v); | ||
+ | Left_Heap::merge(rt,rt,idx); | ||
+ | sz++; | ||
+ | } | ||
+ | void merge(Heap y){ | ||
+ | Left_Heap::merge(rt,rt,y.rt); | ||
+ | sz+=y.sz; | ||
+ | } | ||
+ | Heap(){sz=rt=0;} | ||
+ | }heap[MAXN]; | ||
+ | struct Edge{ | ||
+ | int to,next; | ||
+ | }edge[MAXN]; | ||
+ | int head[MAXN],edge_cnt; | ||
+ | void Insert(int u,int v){ | ||
+ | edge[++edge_cnt]=Edge{v,head[u]}; | ||
+ | head[u]=edge_cnt; | ||
+ | } | ||
+ | int a[MAXN],s[MAXN],d[MAXN],ans1[MAXN],ans2[MAXN]; | ||
+ | LL h[MAXN],tag[MAXN]; | ||
+ | void dfs(int u){ | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | d[v]=d[u]+1; | ||
+ | dfs(v); | ||
+ | heap[u].merge(heap[v]); | ||
+ | } | ||
+ | while(heap[u].sz&&heap[u].top().second<h[u]){ | ||
+ | ans1[u]++; | ||
+ | ans2[heap[u].top().first]=d[u]; | ||
+ | heap[u].pop(); | ||
+ | } | ||
+ | if(heap[u].sz){ | ||
+ | if(a[u]) | ||
+ | Left_Heap::push_tag(heap[u].rt,tag[u],0); | ||
+ | else | ||
+ | Left_Heap::push_tag(heap[u].rt,1,tag[u]); | ||
+ | } | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | Left_Heap::init(); | ||
+ | int n=read_int(),m=read_int(); | ||
+ | _rep(i,1,n) | ||
+ | h[i]=read_LL(); | ||
+ | _rep(i,2,n){ | ||
+ | Insert(read_int(),i); | ||
+ | a[i]=read_int(),tag[i]=read_LL(); | ||
+ | } | ||
+ | _rep(i,1,m){ | ||
+ | LL c=read_LL(); | ||
+ | s[i]=read_int(); | ||
+ | heap[s[i]].push(i,c); | ||
+ | } | ||
+ | d[1]=1; | ||
+ | dfs(1); | ||
+ | _rep(i,1,n) | ||
+ | enter(ans1[i]); | ||
+ | _rep(i,1,m) | ||
+ | enter(d[s[i]]-ans2[i]); | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> |