F - 八苦を滅した尼公 POJ - 2763 线段树LCA-白红宇

F - 八苦を滅した尼公 POJ - 2763 线段树LCA

阅读量：4681 次

发布时间：2019-06-09

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

//#include
     
      //#pragma comment(linker, "/STACK:1024000000,1024000000") #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                using namespace std;#define ll long long#define pb push_backconst int maxn=1e6+7;const int inf=0x3f3f3f3f;struct EDGE{ int u,v,val,next;}G[maxn<<1];int tot;int head[maxn];void init(){ memset(head,-1,sizeof head);tot=0;}void addedge(int u,int v,int w){ tot++;G[tot]={u,v,w,head[u]};head[u]=tot;}int vs[maxn<<1];int in[maxn],out[maxn];int tim; int dep[maxn<<1];int id[maxn];int pre[maxn];void dfs(int u,int fa,int d){ pre[u]=fa; id[u]=++tim;vs[tim]=u;dep[tim]=d; in[u]=tim;out[u]=tim; for(int i=head[u];~i;i=G[i].next){ EDGE e=G[i]; if(e.v==fa)continue; dfs(e.v,u,d+e.val); vs[++tim]=u;dep[tim]=d;out[u]=tim; }}struct node{ int fa; //区间内公共祖先 int mindep; int add; //lazy}ST[maxn<<2];void pushdown(int rt){ if(ST[rt].add){ ST[rt<<1].mindep+=ST[rt].add;ST[rt<<1|1].mindep+=ST[rt].add; ST[rt<<1].add+=ST[rt].add;ST[rt<<1|1].add+=ST[rt].add; ST[rt].add=0; }}void pushup(int rt){ if(ST[rt<<1].mindep<=ST[rt<<1|1].mindep){ ST[rt].mindep=ST[rt<<1].mindep; ST[rt].fa=ST[rt<<1].fa; }else{ ST[rt].mindep=ST[rt<<1|1].mindep; ST[rt].fa=ST[rt<<1|1].fa; }}void build(int l,int r,int rt){ if(l==r){ ST[rt].mindep=dep[l]; ST[rt].fa=vs[l]; ST[rt].add=0; return; } ST[rt].add=0; int m=l+r>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt);}void update(int a,int b,int c,int l,int r,int rt){ if(a<=l&&b>=r){ ST[rt].mindep+=c; ST[rt].add+=c; return; } pushdown(rt); int m=l+r>>1; if(a<=m)update(a,b,c,l,m,rt<<1); if(b>m)update(a,b,c,m+1,r,rt<<1|1); pushup(rt);}node query(int a,int b,int l,int r,int rt){ //查询a-b内的祖先 //cout<
                <<" "<<<" "<
                  
                   <<" "<
                   
                    <
                    
                     =r){ return ST[rt]; } pushdown(rt); int m=l+r>>1; node n2={0,inf,0},n1={0,inf,0}; if(a<=m)n1=query(a,b,l,m,rt<<1); if(b> m)n2=query(a,b,m+1,r,rt<<1|1); if(n1.mindep
                     
                      v)swap(u,v); addedge(u,v,w); addedge(v,u,w); } int now=s; tim=0; dep[s]=0; dfs(s,s,0); build(1,tim,1); for(int i=1;i<=q;i++){ int kind;int a,b; scanf("%d",&kind); if(kind){ //改边 scanf("%d%d",&a,&b); a=2*a-1; int flag=0; if(pre[G[a].v]==G[a].u){flag=1;} else a++; EDGE e=G[a]; int plus=b-e.val; update(in[e.v],out[e.v],plus,1,tim,1); if(flag){ G[a].val=b; G[a+1].val=b; }else{ G[a].val=b; G[a-1].val=b; } //for(int i=1;i<=tim;i++){ // cout<
                      
                       <<"ss"<