线段树相关

P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴 #include using namespace std; #define int long long #define lc(x) tr[x].l #define rc(x) tr[x].r const int N=1e5+5; int n,m,idx; int fa[N],top[N],siz[N],son[N],dep[N]; int ans[N],rt[N]; vector t[N]; struct tree{ int l,r,sum,typ; }tr[N*50]; void pushup(int p){ if(tr[lc(p)].sum>=tr[rc(p)].sum){ tr[p].sum=tr[lc(p)].sum; tr[p].typ=tr[lc(p)].typ; } else{ tr[p].sum=tr[rc(p)].sum; tr[p].typ=tr[rc(p)].typ; } } void change(int &p,int l,int r,int z,int k){ if(!p) p=++idx; if(l==r){ tr[p].sum+=k; tr[p].typ=z; return; } int mid=l+r>>1; if(z>1; tr[x].l=merge(lc(x),lc(y),l,mid); tr[x].r=merge(rc(x),rc(y),mid+1,r); pushup(x); return x; } void dfs1(int u){ siz[u]=1,dep[u]=dep[fa[u]]+1; for(int i=0;isiz[son[u]]) son[u]=v; } } void dfs2(int u,int topf){ top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=0;i>n>>m; for(int i=1;i>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1); dfs2(1,1); while(m--){ int x,y,z; cin>>x>>y>>z; change(rt[x],1,N,z,1); change(rt[y],1,N,z,1); int LCA=lca(x,y); change(rt[LCA],1,N,z,-1); change(rt[fa[LCA]],1,N,z,-1); } dfs3(1); for(int i=1;i `#include using namespace std; #define int long long #define lc(x) tr[x].l #define rc(x) tr[x].r const int N=1e5+5; int n,m,idx; int fa[N],top[N],siz[N],son[N],dep[N]; int ans[N],rt[N]; vectorint> t[N]; struct tree{ int l,r,sum,typ; }tr[N*50]; void pushup(int p){ if(tr[lc(p)].sum>=tr[rc(p)].sum){ tr[p].sum=tr[lc(p)].sum; tr[p].typ=tr[lc(p)].typ; } else{ tr[p].sum=tr[rc(p)].sum; tr[p].typ=tr[rc(p)].typ; } } void change(int &p,int l,int r,int z,int k){ if(!p) p=++idx; if(l==r){ tr[p].sum+=k; tr[p].typ=z; return; } int mid=l+r>>1; if(zchange(lc(p),l,mid,z,k); else change(rc(p),mid+1,r,z,k); pushup(p); } int merge(int x,int y,int l,int r){ if(!x||!y) return x+y; if(l==r){ tr[x].sum+=tr[y].sum; return x; } int mid=l+r>>1; tr[x].l=merge(lc(x),lc(y),l,mid); tr[x].r=merge(rc(x),rc(y),mid+1,r); pushup(x); return x; } void dfs1(int u){ siz[u]=1,dep[u]=dep[fa[u]]+1; for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==fa[u]) continue; fa[v]=u; dfs1(v); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int topf){ top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]dep[top[y]]) swap(x,y); x=fa[top[x]]; } return (dep[x]dep[y]?x:y); } void dfs3(int u){ for(int i=0;it[u].size();i++){ int v=t[u][i]; if(v==fa[u]) continue; dfs3(v); rt[u]=merge(rt[u],rt[v],1,N); } if(tr[rt[u]].sum) ans[u]=tr[rt[u]].typ; else ans[u]=0; } signed main(){ cin>>n>>m; for(int i=1;i int u,v; cin>>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1); dfs2(1,1); while(m--){ int x,y,z; cin>>x>>y>>z; change(rt[x],1,N,z,1); change(rt[y],1,N,z,1); int LCA=lca(x,y); change(rt[LCA],1,N,z,-1); change(rt[fa[LCA]],1,N,z,-1); } dfs3(1); for(int i=1;ians[i]'\n'; return 0; } ` P5494 【模板】线段树分裂 #include using namespace std; #define int long long #define lc(x) tr[x].l #define rc(x) tr[x].r const int N=2e5+5; int n,m,idx,cnt=1; int rt[N]; struct tree{ int l,r,sum; }tr[N*50]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void add(int &p,int l,int r,int x,int k){ if(!p) p=++idx; tr[p].sum+=k; if(l==r) return; int mid=l+r>>1; if(x=L&&r>1,ans=0; if(Lmid) ans+=query(rc(p),mid+1,r,L,R); return ans; } void split(int x,int &y,int k){ //x中前k个留在x，后面的分给y if(tr[x].sum==k) return; if(!y) y=++idx; int s=tr[lc(x)].sum; if(k>1; tr[x].l=merge(lc(x),lc(y),l,mid); tr[x].r=merge(rc(x),rc(y),mid+1,r); pushup(x); return x; } int check(int p,int l,int r,int k){ if(k>tr[p].sum) return -1; if(l==r) return l; int mid=l+r>>1,s=tr[lc(p)].sum; if(k>n>>m; for(int i=1;i>x; add(rt[1],1,n,i,x); } while(m--){ int op; cin>>op; if(op==0){ int p,x,y; cin>>p>>x>>y; int s1=query(rt[p],1,n,1,y); int s2=query(rt[p],1,n,x,y); int t=0; split(rt[p],rt[++cnt],s1-s2); split(rt[cnt],t,s2); rt[p]=merge(rt[p],t,1,n); } if(op==1){ int p,t; cin>>p>>t; rt[p]=merge(rt[p],rt[t],1,n); } if(op==2){ int p,x,q; cin>>p>>x>>q; add(rt[p],1,n,q,x); } if(op==3){ int p,x,y; cin>>p>>x>>y; cout>p>>k; cout `#include using namespace std; #define int long long #define lc(x) tr[x].l #define rc(x) tr[x].r const int N=2e5+5; int n,m,idx,cnt=1; int rt[N]; struct tree{ int l,r,sum; }tr[N*50]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void add(int &p,int l,int r,int x,int k){ if(!p) p=++idx; tr[p].sum+=k; if(l==r) return; int mid=l+r>>1; if(xadd(lc(p),l,mid,x,k); else add(rc(p),mid+1,r,x,k); pushup(p); } int query(int p,int l,int r,int L,int R){ if(l>=L&&rreturn tr[p].sum; int mid=l+r>>1,ans=0; if(Lquery(lc(p),l,mid,L,R); if(R>mid) ans+=query(rc(p),mid+1,r,L,R); return ans; } void split(int x,int &y,int k){ //x中前k个留在x，后面的分给y if(tr[x].sum==k) return; if(!y) y=++idx; int s=tr[lc(x)].sum; if(ksplit(lc(x),lc(y),k),swap(rc(x),rc(y)); else split(rc(x),rc(y),k-s); tr[y].sum=tr[x].sum-k; tr[x].sum=k; } int merge(int x,int y,int l,int r){ if(!x||!y) return x+y; if(l==r){ tr[x].sum+=tr[y].sum; return x; } int mid=l+r>>1; tr[x].l=merge(lc(x),lc(y),l,mid); tr[x].r=merge(rc(x),rc(y),mid+1,r); pushup(x); return x; } int check(int p,int l,int r,int k){ if(k>tr[p].sum) return -1; if(l==r) return l; int mid=l+r>>1,s=tr[lc(p)].sum; if(kreturn check(lc(p),l,mid,k); else return check(rc(p),mid+1,r,k-s); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i int x; cin>>x; add(rt[1],1,n,i,x); } while(m--){ int op; cin>>op; if(op==0){ int p,x,y; cin>>p>>x>>y; int s1=query(rt[p],1,n,1,y); int s2=query(rt[p],1,n,x,y); int t=0; split(rt[p],rt[++cnt],s1-s2); split(rt[cnt],t,s2); rt[p]=merge(rt[p],t,1,n); } if(op==1){ int p,t; cin>>p>>t; rt[p]=merge(rt[p],rt[t],1,n); } if(op==2){ int p,x,q; cin>>p>>x>>q; add(rt[p],1,n,q,x); } if(op==3){ int p,x,y; cin>>p>>x>>y; coutquery(rt[p],1,n,x,y)"\n"; } if(op==4){ int p,k; cin>>p>>k; coutcheck(rt[p],1,n,k)"\n"; } } return 0; }` P5787 【模板】线段树分治 / 二分图 #include using namespace std; #define lc (p st; vector> tr[N]; int n,m,k; int f[N],siz[N],ans[N]; void insert(int p,int l,int r,int x,int y, pair e){ if(x>r || y>1; insert(lc,l,mid,x,y,e); insert(rc,mid+1,r,x,y,e); } int find(int x){ while(x!=f[x]) x=f[x]; return f[x]; } void merge(int x,int y){ x=find(x); y=find(y); if(siz[x]>siz[y]) swap(x,y); st.push({x,y,siz[y]}); f[x]=y; siz[y]+=(siz[x]==siz[y]); } void check(int p,int l,int r){ int flag=0; int now=st.size(); for(int i=0;i e=tr[p][i]; merge(e.first,e.second+n); merge(e.second,e.first+n); if(find(e.first)==find(e.second)){ flag=1; break; } } if(!flag){ if(l==r) ans[l]=1; else{ int mid=l+r>>1; check(lc,l,mid); check(rc,mid+1,r); } } while(st.size()>now){ node t=st.top(); st.pop(); f[t.x]=t.x; siz[t.y]=t.hy; } } int main(){ cin>>n>>m>>k; for(int i=1;i>x>>y>>l>>r; insert(1,1,k,l+1,r,{x,y}); } check(1,1,k); for(int i=1;i `#include using namespace std; #define lc (p #define rc (p const int N=4e6+5; struct node{ int x,y,hy; }; stack st; vectorint,int>> tr[N]; int n,m,k; int f[N],siz[N],ans[N]; void insert(int p,int l,int r,int x,int y, pairint,int> e){ if(x>r || yreturn; if(xreturn tr[p].push_back(e); int mid=l+r>>1; insert(lc,l,mid,x,y,e); insert(rc,mid+1,r,x,y,e); } int find(int x){ while(x!=f[x]) x=f[x]; return f[x]; } void merge(int x,int y){ x=find(x); y=find(y); if(siz[x]>siz[y]) swap(x,y); st.push({x,y,siz[y]}); f[x]=y; siz[y]+=(siz[x]==siz[y]); } void check(int p,int l,int r){ int flag=0; int now=st.size(); for(int i=0;itr[p].size();i++){ pairint,int> e=tr[p][i]; merge(e.first,e.second+n); merge(e.second,e.first+n); if(find(e.first)==find(e.second)){ flag=1; break; } } if(!flag){ if(l==r) ans[l]=1; else{ int mid=l+r>>1; check(lc,l,mid); check(rc,mid+1,r); } } while(st.size()>now){ node t=st.top(); st.pop(); f[t.x]=t.x; siz[t.y]=t.hy; } } int main(){ cin>>n>>m>>k; for(int i=1;i2*n;i++) f[i]=i; for(int i=1;i int x,y,l,r; cin>>x>>y>>l>>r; insert(1,1,k,l+1,r,{x,y}); } check(1,1,k); for(int i=1;i if(ans[i]) cout"Yes\n"; else cout"No\n"; } re…