高级数据结构源代码.rar

//线段树扩展 //可以计算长度和线段数 //可以处理加入边和删除边不同的情况 //inc_seg和dec_seg用于加入边 //seg_len求长度,seg_cut求线段数 //t传根节点(一律为1) //l0,r0传树的节点范围(一律为1..t) //l,r传线段(端点) #define MAXN 10000 struct segtree{ int n,cnt[MAXN],len[MAXN],cut[MAXN],bl[MAXN],br[MAXN]; segtree(int t):n(t){ for (int i=1;i<=t;i++) cnt[i]=len[i]=cut[i]=bl[i]=br[i]=0; }; void update(int t,int l,int r); void inc_seg(int t,int l0,int r0,int l,int r); void dec_seg(int t,int l0,int r0,int l,int r); int seg_len(int t,int l0,int r0,int l,int r); int seg_cut(int t,int l0,int r0,int l,int r); }; int length(int l,int r){ return r-l; } void segtree::update(int t,int l,int r){ if (cnt[t]||r-l==1) len[t]=length(l,r),cut[t]=bl[t]=br[t]=1; else{ len[t]=len[t+t]+len[t+t+1]; cut[t]=cut[t+t]+cut[t+t+1]; if (br[t+t]&&bl[t+t+1]) cut[t]--; bl[t]=bl[t+t],br[t]=br[t+t+1]; } } void segtree::inc_seg(int t,int l0,int r0,int l,int r){ if (l0==l&&r0==r) cnt[t]++; else{ int m0=(l0+r0)>>1; if (l<m0) inc_seg(t+t,l0,m0,l,m0<r?m0:r); if (r>m0) inc_seg(t+t+1,m0,r0,m0>l?m0:l,r); if (cnt[t+t]&&cnt[t+t+1]){ cnt[t+t]--; update(t+t,l0,m0); cnt[t+t+1]--; update(t+t+1,m0,r0); cnt[t]++; } } update(t,l0,r0); } void segtree::dec_seg(int t,int l0,int r0,int l,int r){ if (l0==l&&r0==r) cnt[t]--; else if (cnt[t]){ cnt[t]--; if (l>l0) inc_seg(t,l0,r0,l0,l); if (r<r0) inc_seg(t,l0,r0,r,r0); } else{ int m0=(l0+r0)>>1; if (l<m0) dec_seg(t+t,l0,m0,l,m0<r?m0:r); if (r>m0) dec_seg(t+t+1,m0,r0,m0>l?m0:l,r); } update(t,l0,r0); } int segtree::seg_len(int t,int l0,int r0,int l,int r){ if (cnt[t]||(l0==l&&r0==r)) return len[t]; else{ int m0=(l0+r0)>>1,ret=0; if (l<m0) ret+=seg_len(t+t,l0,m0,l,m0<r?m0:r); if (r>m0) ret+=seg_len(t+t+1,m0,r0,m0>l?m0:l,r); return ret; } } int segtree::seg_cut(int t,int l0,int r0,int l,int r){ if (cnt[t]) return 1; if (l0==l&&r0==r) return cut[t]; else{ int m0=(l0+r0)>>1,ret=0; if (l<m0) ret+=seg_cut(t+t,l0,m0,l,m0<r?m0:r); if (r>m0) ret+=seg_cut(t+t+1,m0,r0,m0>l?m0:l,r); if (l<m0&&r>m0&&br[t+t]&&bl[t+t+1]) ret--; return ret; } }