雨天的尾巴-白红宇

雨天的尾巴

阅读量：4665 次

发布时间：2019-06-09

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

线段树合并模板题

不说了直接代码分析

大佬的code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define ll long long#define N 101000#define Z 100000#define inf 1e9#define RG register#define re returninline ll read(){ RG ll x=0,t=1;RG 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;}int n,m,top,first[N],ans[N];struct mona { int nxt,en;}s[N<<1];struct joker{ int nxt,en,op;};inline void Insert(int x,int y) { s[++top]=(mona){first[x],y}; first[x]=top; }struct SeqTree{ int cnt,ls[N*40],rs[N*40],Max[N*40],id[N*40],rt[N],rab[N*40],tot,top,first[N]; joker s[N<<2]; inline void Insert(int x,int y,int op) //差分起始 { s[++top]=(joker){first[x],y,op}; first[x]=top; } inline int New() { if(tot) re rab[tot--]; re ++cnt; } inline void Throw(int x) { rab[++top]=x; ls[x]=rs[x]=Max[x]=id[x]=0; } inline void Pushup(int x) { if(Max[ls[x]]>=Max[rs[x]]) Max[x]=Max[ls[x]],id[x]=id[ls[x]]; else Max[x]=Max[rs[x]],id[x]=id[rs[x]]; } inline void Modify(int l,int r,int &x,int pos,int val) { if(!x) x=New(); if(l==r) { Max[x]+=val; id[x]=l; } else { int mid=l+r>>1; if(pos<=mid) Modify(l,mid,ls[x],pos,val); else Modify(mid+1,r,rs[x],pos,val); Pushup(x); } if(!Max[x]) id[x]=0;//回收机制处理 } inline int Merge(int l,int r,int u,int v)//并一波线段树 { if(!u||!v) return u|v; int now=New(),mid=l+r>>1; if(l==r) Max[now]=Max[u]+Max[v],id[now]=l;//MAX,id同步 else { ls[now]=Merge(l,mid,ls[u],ls[v]); rs[now]=Merge(mid+1,r,rs[u],rs[v]); Pushup(now); } Throw(u); Throw(v); //biu,扔进垃圾桶 re now; }} T;struct Tree{ int top[N],son[N],siz[N],fa[N],dep[N]; inline void Dfs(int k,int Fa){ fa[k]=Fa,siz[k]=1,dep[k]=dep[Fa]+1; for(RG int i=first[k];i;i=s[i].nxt){ int en=s[i].en; if(en==Fa) continue ; Dfs(en,k),siz[k]+=siz[en]; if(siz[son[k]]

蒟蒻的

有一点问题就是

权值线段树

貌似可以不用离散化

/*while(next second)++love_life;*/#include
     
      #define re return#define R register #define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=1e5+5,maxl=1e5;int n,m,k,hd[maxn],hide[maxn],X[maxn],Y[maxn],Z[maxn],a[maxn];int ans[maxn];struct node{    int to,nt;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}struct tree{    int first[maxn],top,tot,cnt;    int rab[maxn*30],rt[maxn*30],id[maxn*30],ls[maxn*30],rs[maxn*30],Max[maxn*30];    struct LL    {        int col,nt,op;    }st[maxn<<2];        inline void insert(int x,int y,int z)    //节点X染成y，+-z     {        st[++top].col=y;st[top].nt=first[x];first[x]=top;st[top].op=z;    }        inline int New()    {        int now;        if(tot)now=rab[tot--];        else now=++cnt;        ls[now]=rs[now]=Max[now]=0;        re now;    }        inline void Throw(int x)    {        rab[++tot]=x;    }        inline void pushup(int rt)    {        if(Max[ls[rt]]
       
        >1;        if(pos<=mid) Add(ls[rt],l,mid,pos,val);        else Add(rs[rt],mid+1,r,pos,val);        pushup(rt);        if(!Max[rt]) id[rt]=0;    }        inline int merge(int l,int r,int x,int y)    {        if(!x||(!y))re x+y;        if(l==r)        {            Max[x]+=Max[y];            Throw(y);            re x;        }                int mid=(l+r)>>1;        ls[x]=merge(l,mid,ls[x],ls[y]);        rs[x]=merge(mid+1,r,rs[x],rs[y]);        Throw(y);        pushup(x);        re x;    }    }T;struct LCA{    int fa[maxn],top[maxn],son[maxn],size[maxn],dep[maxn];        inline void dfs1(int x)    {        dep[x]=dep[fa[x]]+(size[x]=1);        for(int i=hd[x];i;i=e[i].nt)        {            int v=e[i].to;            if(v==fa[x])continue;            fa[v]=x;            dfs1(v);            size[x]+=size[v];            if(size[v]>size[son[x]])            son[x]=v;        }    }        inline void dfs2(int x,int topf)    {        top[x]=topf;        if(son[x])        {            dfs2(son[x],topf);            for(int i=hd[x];i;i=e[i].nt)            {                int v=e[i].to;                if(!top[v])                dfs2(v,v);            }        }        }        inline int Lca(int x,int y)    {        while(top[x]!=top[y])        {            if(dep[top[x]]