ZR 集训 Day6 - 可持久化、虚树 · ooliver

ZR 集训 Day6 - 可持久化、虚树 SP11470 TTM - To the moon 可持久化线段树题。会发现对于区间修改我们是需要懒标记的，但是对一个版本打了懒标记后下传可能会影响其他版本。这里用到了标记永久化的思想，打上懒标记后不下传，而是在统计答案时递归作为参数下传。代码： C++ #include using namespace std; #define int long long #define lc(p) tr[p].ls #define rc(p) tr[p].rs const int N=1e5+5; int n,m,idx,t,now; int rt[N],a[N]; struct tree{ int l,r,ls,rs,sum,lz; void tag(int k){ sum+=(r-l+1)*k; lz+=k; } }tr[N*32]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void build(int &p,int l,int r){ p=++idx,tr[p].l=l,tr[p].r=r; if(l==r){ tr[p].sum=a[l]; return; } int mid=l+r>>1; build(lc(p),l,mid); build(rc(p),mid+1,r); pushup(p); } void add(int f,int &p,int x,int y,int k){ p=++idx,tr[p]=tr[f]; if(tr[p].l>=x&&tr[p].r>1; if(xmid) add(rc(f),rc(p),x,y,k); } int qry(int p,int x,int y,int tag){ if(tr[p].l>=x&&tr[p].r>1,res=0; if(xmid) res+=qry(rc(p),x,y,tag+tr[p].lz); return res; } signed main(){ cin>>n>>m; for(int i=1;i>a[i]; build(rt[0],1,n); while(m--){ char op; int l,r,x; cin>>op; if(op=='C'){ cin>>l>>r>>x; p[++now]=++t; add(rt[t-1],rt[t],l,r,x); } if(op=='Q'){ cin>>l>>r; cout>l>>r>>x; cout>t; } } return 0; } `#include using namespace std; #define int long long #define lc(p) tr[p].ls #define rc(p) tr[p].rs const int N=1e5+5; int n,m,idx,t,now; int rt[N],a[N]; struct tree{ int l,r,ls,rs,sum,lz; void tag(int k){ sum+=(r-l+1)*k; lz+=k; } }tr[N*32]; void pushup(int p){ tr[p].sum=tr[lc(p)].sum+tr[rc(p)].sum; } void build(int &p,int l,int r){ p=++idx,tr[p].l=l,tr[p].r=r; if(l==r){ tr[p].sum=a[l]; return; } int mid=l+r>>1; build(lc(p),l,mid); build(rc(p),mid+1,r); pushup(p); } void add(int f,int &p,int x,int y,int k){ p=++idx,tr[p]=tr[f]; if(tr[p].l>=x&&tr[p].ry){ tr[p].tag(k); return; } tr[p].sum+=(min(y,tr[p].r)-max(x,tr[p].l)+1)*k; int mid=tr[p].l+tr[p].r>>1; if(xmid) add(lc(f),lc(p),x,y,k); if(y>mid) add(rc(f),rc(p),x,y,k); } int qry(int p,int x,int y,int tag){ if(tr[p].l>=x&&tr[p].ry) return tr[p].sum+tag*(tr[p].r-tr[p].l+1); int mid=tr[p].l+tr[p].r>>1,res=0; if(xmid) res+=qry(lc(p),x,y,tag+tr[p].lz); if(y>mid) res+=qry(rc(p),x,y,tag+tr[p].lz); return res; } signed main(){ cin>>n>>m; for(int i=1;in;i++) cin>>a[i]; build(rt[0],1,n); while(m--){ char op; int l,r,x; cin>>op; if(op=='C'){ cin>>l>>r>>x; p[++now]=++t; add(rt[t-1],rt[t],l,r,x); } if(op=='Q'){ cin>>l>>r; coutqry(rt[t],l,r,0)"\n"; } if(op=='H'){ cin>>l>>r>>x; coutqry(rt[x],l,r,0)"\n"; } if(op=='B'){ cin>>t; } } return 0; }` P4216 [SCOI2015] 情报传递这道题大部分人应该都是写的对树上每颗节点为版本建主席树的离线 O(n\log n) 做法，但是个人认为树剖+以时间为历史版本建主席树似乎更好想也更好写一点，并且这种方法是在线的，虽然复杂度是 O(n\log ^2 n) 的，但是实测比大部分 O(n\log n) 做法还要快。代码： C++ #include using namespace std; #define pii pair #define fi first #define sc second #define lc(p) tr[p].ls #define rc(p) tr[p].rs const int N=2e5+5; int n,q,t0,idx,now; int rt[N],a[N],tag[N],son[N],dfn[N],siz[N],top[N],dep[N],fa[N]; vector t[N]; struct tree{ int ls,rs,sum; }tr[N*32]; void dfs1(int u,int f){ siz[u]=1,dep[u]=dep[f]+1; for(int v:t[u]){ dfs1(v,u); if(siz[v]>siz[son[u]]) son[u]=v; siz[u]+=siz[v]; } } void dfs2(int u,int topf){ top[u]=topf,dfn[u]=++idx; if(son[u]) dfs2(son[u],topf); for(int v:t[u]){ if(v==son[u]) continue; dfs2(v,v); } } void add(int f,int &p,int l,int r,int x){ p=++idx,tr[p]=tr[f],tr[p].sum++; if(l==x&&r==x) return; int mid=(l+r)>>1; if(x=x&&r>1,res=0; if(xmid) res+=qry(rc(p),x,y,mid+1,r); return res; } pii path(int x,int y,int t){ int sum=0,res=0; while(top[x]!=top[y]){ if(dep[top[x]]dfn[y]) swap(x,y); res+=qry(rt[t],dfn[x],dfn[y],1,n); sum+=dfn[y]-dfn[x]+1; return {sum,res}; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i>fa[i]; if(fa[i]) t[fa[i]].push_back(i); else t0=i; } dfs1(t0,0); dfs2(t0,t0); idx=0; cin>>q; for(int i=1,op,x,y,z;i>op; if(op==1){ cin>>x>>y>>z; pii ans=path(x,y,max(i-z-1,0)); cout>x; if(!tag[x]) add(rt[i-1],rt[i],1,n,dfn[x]),tag[x]=1; else rt[i]=rt[i-1]; } } return 0; } `#include using namespace std; #define pii pair #define fi first #define sc second #define lc(p) tr[p].ls #define rc(p) tr[p].rs const int N=2e5+5; int n,q,t0,idx,now; int rt[N],a[N],tag[N],son[N],dfn[N],siz[N],top[N],dep[N],fa[N]; vectorint> t[N]; struct tree{ int ls,rs,sum; }tr[N*32]; void dfs1(int u,int f){ siz[u]=1,dep[u]=dep[f]+1; for(int v:t[u]){ dfs1(v,u); if(siz[v]>siz[son[u]]) son[u]=v; siz[u]+=siz[v]; } } void dfs2(int u,int topf){ top[u]=topf,dfn[u]=++idx; if(son[u]) dfs2(son[u],topf); for(int v:t[u]){ if(v==son[u]) continue; dfs2(v,v); } } void add(int f,int &p,int l,int r,int x){ p=++idx,tr[p]=tr[f],tr[p].sum++; if(l==x&&r==x) return; int mid=(l+r)>>1; if(xmid) add(lc(f),lc(p),l,mid,x); else add(rc(f),rc(p),mid+1,r,x); } int qry(int p,int x,int y,int l,int r){ if(l>=x&&ry) return tr[p].sum; int mid=(l+r)>>1,res=0; if(xmid) res+=qry(lc(p),x,y,l,mid); if(y>mid) res+=qry(rc(p),x,y,mid+1,r); return res; } pii path(int x,int y,int t){ int sum=0,res=0; while(top[x]!=top[y]){ if(dep[top[x]]dep[top[y]]) swap(x,y); res+=qry(rt[t],dfn[top[x]],dfn[x],1,n); sum+=dfn[x]-dfn[top[x]]+1; x=fa[top[x]]; } if(dfn[x]>dfn[y]) swap(x,y); res+=qry(rt[t],dfn[x],dfn[y],1,n); sum+=dfn[y]-dfn[x]+1; return {sum,res}; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;in;i++){ cin>>fa[i]; if(fa[i]) t[fa[i]].push_back(i); else t0=i; } dfs1(t0,0); dfs2(t0,t0); idx=0; cin>>q; for(int i=1,op,x,y,z;iq;i++){ cin>>op; if(op==1){ cin>>x>>y>>z; pii ans=path(x,y,max(i-z-1,0)); coutans.fi" "ans.sc"\n"; rt[i]=rt[i-1]; } else{ cin>>x; if(!tag[x]) add(rt[i-1],rt[i],1,n,dfn[x]),tag[x]=1; else rt[i]=rt[i-1]; } } return 0; }` P10634 BZOJ2372 music 不难想到 KMP，只是把配对的相等条件换为了排名相等，树状数组维护即可。代码： C++ #include using namespace std; #define lowbit(x) x&-x const int N=5e5+5; int n,m,s,idx; int a[N],b[N],nxt[N],ans[N]; struct BIT{ int t[N]; void add(int x,int k){ for(int i=x;i0;i-=lowbit(i)) res+=t[i]; return res; } void clear(){ memset(t,0,sizeof t); } }A,B; int main(){ cin>>n>>m>>s; for(int i=0;i>b[i]; for(int i=0;i>a[i]; int i=1,j=0; while(i `#include using namespace std; #define lowbit(x) x&-x const int N=5e5+5; int n,m,s,idx; int a[N],b[N],nxt[N],ans[N]; struct BIT{ int t[N]; void add(int x,int k){ for(int i=x;iN;i+=lowbit(i)) t[i]+=k; } int get(int x){ if(x==0) return 0; int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=t[i]; return res; } void clear(){ memset(t,0,sizeof t); } }A,B; int main(){ cin>>n>>m>>s; for(int i=0;in;i++) cin>>b[i]; for(int i=0;im;i++) cin>>a[i]; int i=1,j=0; while(im){ if(A.get(a[j]-1)==B.get(a[i]-1)&&A.get(a[j])==B.get(a[i])){ B.add(a[i],1),A.add(a[j],1); j++,nxt[i++]=j; } else{ if(j==0){ nxt[i++]=0; continue; } int len=j-nxt[j-1]; for(int k=0;klen;k++){ A.add(a[j-1-k],-1); B.add(a[i-j+k],-1); } j=nxt[j-1]; } } A.clear(),B.clear(); i=0,j=0; while(in){ if(A.get(a[j]-1)==B.get(b[i]-1)&&A.get(a[j])==B.get(b[i])){ B.add(b[i],1),A.add(a[j],1); i++,j++; } else{ if(j==0){ i++; continue; } int len=j-nxt[j-1]; for(int k=0;klen;k++){ A.add(a[j-1-k],-1); B.add(b[i-j+k],-1); } j=nxt[j-1]; } if(j==m){ int len=m-nxt[m-1]; for(int k=0;klen;k++){ A.add(a[m-1-k],-1); B.add(b[i-m+k],-1); } ans[++idx]=i-j+1; j=nxt[j-1]; } } coutidx"\n"; for(int i=1;iidx;i++) coutans[i]"\n"; return 0; }` P5283 [十二省联考 2019] 异或粽子可持久化 01-Trie（话说 01-Trie 和权值线段树没什么区别）。看到区间异或考虑先求出异或前缀和，就变成了两点问题。对每个 i 求出最与其异或和大的 $j(j代码： C++ #include using namespace std; #define int long long const int N=5e5+5; int n,k,idx; int a[N],b[N],rt[N],ch[N*40][2],sz[N*40]; priority_queue> q; int newu(int u){ ++idx,sz[idx]=sz[u],ch[idx][0]=ch[u][0],ch[idx][1]=ch[u][1]; return idx; } int insert(int u,int x,int d=31){ if(d==-1){ int u2=newu(u); sz[u2]++; return u2; } int u2=newu(u); ch[u2][x>>d&1]=insert(ch[u2][x>>d&1],x,d-1); sz[u2]++; return u2; } int query(int u,int x,int rk,int d=31){ if(d==-1) return 0; int xd=x>>d&1; if(rk>n>>k; rt[0]=insert(rt[0],0); for(int i=1;i>a[i]; a[i]^=a[i-1]; rt[i]=insert(rt[i-1],a[i]); } for(int i=1;i `#include using namespace std; #define int long long const int N=5e5+5; int n,k,idx; int a[N],b[N],rt[N],ch[N*40][2],sz[N*40]; priority_queuepairint,int>> q; int newu(int u){ ++idx,sz[idx]=sz[u],ch[…