hdu3966_树链剖分

最近在强化知识点深度，发现树链剖分不是很会写了。

回顾一下修改操作：

若两个点在同一条链上，则直接修改这段区间。

若不在同一条链上，修改深度较大的点到其链顶端的区间，同时将这个点变为他所在链顶端的父亲，循环操作直到这两个点在同一条链上，就可以用上一种方法了。

没有用LCA写是因为以前被坑过，不但没有这种方法好写，效率也不太让人满意。

主要是对第二种情况如何写有所遗忘，写道模版再给自己提个醒。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           using namespace std; #define MAXN 50005 int n,m,q; vector
          
            map[MAXN]; int size[MAXN],fa[MAXN],son[MAXN],val[MAXN],tid[MAXN],_tid[MAXN],dep[MAXN],top[MAXN]; int cnt; struct node { int l,r,val; }tree[MAXN<<2]; void dfs1(int s,int f,int d) { size[s]=1; fa[s]=f; dep[s]=d; int len=map[s].size(); for(int i=0;i
           
            >1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); } void down(int now) { tree[now<<1].val+=tree[now].val; tree[now<<1|1].val+=tree[now].val; tree[now].val=0; } void update(int l,int r,int now,int num) { if(l==tree[now].l && r==tree[now].r) { tree[now].val+=num; return ; } if(tree[now].val) down(now); int mid=(tree[now].l+tree[now].r)>>1; if(r<=mid) update(l,r,now<<1,num); else if(l>mid) update(l,r,now<<1|1,num); else { update(l,mid,now<<1,num); update(mid+1,r,now<<1|1,num); } } void change(int s,int e,int num) { while(top[s]!=top[e]) { if(dep[top[s]]
            
             dep[e]) swap(s,e); update(tid[s],tid[e],1,num); } int query(int l,int now) { if(tree[now].l==l && tree[now].r==l) return tree[now].val; if(tree[now].val) down(now); int mid=(tree[now].l+tree[now].r)>>1; if(l<=mid) return query(l,now<<1); else return query(l,now<<1|1); } int main() { while(cin>>n>>m>>q) { memset(size,0,sizeof(size)); memset(fa,0,sizeof(fa)); memset(tid,0,sizeof(tid)); memset(son,0,sizeof(son)); cnt=0; for(int i=1;i<=n;i++) { scanf("%d",&val[i]); map[i].clear(); } for(int i=1;i