【BZOJ4538】【HNOI2016】网络（树链剖分，线段树，堆）-白红宇

【BZOJ4538】【HNOI2016】网络（树链剖分，线段树，堆）

阅读量：5105 次

发布时间：2019-06-13

本文共 1945 字，大约阅读时间需要 6 分钟。

题解

树链剖分搞一下LCA

把线段树弄出来

这只是形式上的线段树

本质上是维护一段区间的一个堆

每次把堆插入节点，

询问的时候查询线段树上的堆的最大值就行了

但是在插入节点的时候

把节点插入到非当前树链剖分经过的节点中

这里要稍微处理一下。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #define MAX 110000#define lson (now<<1)#define rson (now<<1|1)using namespace std;inline int read(){ int x=0,t=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}struct Line{ int v,next;}e[MAX*2];struct Link{ int l,r;}li[MAX];struct Record{ int u,v,w;}tt[MAX];inline bool operator <(Link a,Link b){ if(a.l!=b.l)return a.l

Q1; priority_queue

Q2; void push(int x) { Q1.push(x); } void del(int x) { Q2.push(x); } int top() { while(!Q2.empty()&&Q1.top()==Q2.top()){Q1.pop();Q2.pop();} return Q1.empty()?-1:Q1.top(); }}t[MAX*5];int tim,N,M,dfn[MAX];void DFS1(int u,int f){ size[u]=1;dep[u]=dep[f]+1; for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==f)continue; ff[v]=u; DFS1(v,u); size[u]+=size[v]; if(size[v]>size[hson[u]])hson[u]=v; }}void DFS2(int u,int tp){ top[u]=tp;dfn[u]=++tim; if(hson[u])DFS2(hson[u],tp); for(int i=h[u];i;i=e[i].next) { int v=e[i].v; if(v==ff[u]||v==hson[u])continue; DFS2(v,v); }}void Update(int now,int l,int r,int al,int ar,int k,int opt){ if(al==l&&ar==r) { opt?t[now].del(k):t[now].push(k); return; } int mid=(l+r)>>1; if(ar<=mid)Update(lson,l,mid,al,ar,k,opt); else if(al>mid)Update(rson,mid+1,r,al,ar,k,opt); else{Update(lson,l,mid,al,mid,k,opt);Update(rson,mid+1,r,mid+1,ar,k,opt);}}int Query(int now,int l,int r,int x){ if(l==r)return t[now].top(); int mid=(l+r)>>1; int ans=t[now].top(); if(x<=mid)return max(ans,Query(lson,l,mid,x)); else return max(ans,Query(rson,mid+1,r,x));}void Happen(int u,int v,int opt,int xx){ int qq=0; while(top[u]!=top[v]) { if(dep[top[u]]

转载于:https://www.cnblogs.com/cjyyb/p/7623995.html

你可能感兴趣的文章