?? 線段樹擴展.txt
字號:
//線段樹擴展
//可以計算長度和線段數
//可以處理加入邊和刪除邊不同的情況
//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;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -