摘：
主席树思想是每个位置都维护一个线段树，线段树的节点是值的范围，然后第i个线段树中某个区间[x, y]维护的是，1-i中数字在[x, y]范围内的个数。这里利用到了前缀和的思想。
(想学好就得老老实实做笔记，不要相信自己的记忆力。
个人笔记：
关于(静态的)主席树(动态还没学....... )：
1，主席树是高级的权值线段树。
权值线段树区别于普通线段树是：权值线段树是以权值为区间建立起来的线段树，(l,r)是权值区间。其主要作用是记录权值区间里的数出现的总个数，或 单一权值出现的个数。有利于查询<所有权值中>出现的第k大(小)值。
2，主席树和权值线段树关联的地方是，其子结构(主要结构)是权值线段树。
设全局要处理的区间为[1,n]，则n个连续区间[1,x]（1≤x≤n）是n棵权值线段树。
假设真实建立独立的这n棵权值线段树，其消耗空间约为n^2.....
主席树就是，尽量共用节点节省空间建立这n棵线段树，每棵线段树的建立是在上一棵线段树的基础上共用节点建立起来的。
主席树模板题是求区间第k大，设区间为(l,r)，则所求就是 在满足树T[r]与树T[l-1]权值区间 权值数量差为k的条件下 不断缩小的到的 l(r)
3，据说：每棵线段树不一定是由上一时刻转移来的，要因题而异。
4，可持久化线段树的三种建树方法：
(1)、对序列建树，常见方法，每个点一个时刻的树。
(2)、树上主席树，树上每个点一棵线段树，每个点的线段树从父节点修改而来。
(3)、对深度建立主席树，每个深度建立一棵主席树，将该深度的所有点都加进来，当树上问题对深度有限制时用这个。
5，关于树上主席树，学习笔记：参考题目洛谷P2633 Count on a tree
_1，树上主席树的做法通常还涉及两个知识点：
(1) 树上差分。（基于：每个点的线段树是从父节点修改而来，才有效）
目前不懂，只知道对于区间[l,r]，它的直接路径的点数是num[ T[l] ]+num[ T[r] ]-num[ T[lca] ]-num[ T[fa_lca] ];
直接路径的权值和是sum[ T[l] ]+sum[ T[r] ]-sum[ T[lca] ]-sum[ T[fa_lca] ]；
(2) lca是点l和r的最近公共祖先，fa_lca是点lca的直接父亲。num,sum,是主席树统计出来的值。
关于最近公共祖先，我目前的做法是直接套用树链剖分的top[]数组来求，更好的做法似乎是用倍增数组，还不会，待学。
_2，树上主席树的建立方法是通过dfs序来建，但并非真的是dfs序，应该说是，每个节点的线段树是由它的父节点修改而来，树上差分是基于这种做法才有效。
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=5e5+50; const int mod=998244353; int n,a[maxn],h[maxn],nn; vector<int>p[maxn]; int val(int i) { return lower_bound(h+1,h+1+nn,a[i])-h; } int T[maxn],L[maxn*20],R[maxn*20],sum[maxn*20],tot; void build(int& rt,int l,int r) { rt=++tot; sum[rt]=0; if(l==r)return; int mid=(l+r)>>1; build(L[rt],l,mid); build(R[rt],mid+1,r); } void update(int &rt,int l,int r,int pre,int x) { rt=++tot; L[rt]=L[pre]; R[rt]=R[pre]; sum[rt]=sum[pre]+1; if(l==r)return; int mid=(l+r)>>1; if(x<=mid)update(L[rt],l,mid,L[pre],x); else update(R[rt],mid+1,r,R[pre],x); } int query(int x,int y,int lca,int falca,int l,int r,int k) { if(k>sum[x]+sum[y]-sum[lca]-sum[falca])return 0; if(l==r)return l; int mid=(l+r)>>1; int s=sum[L[x]]+sum[L[y]]-sum[L[lca]]-sum[L[falca]]; if(k<=s)return query(L[x],L[y],L[lca],L[falca],l,mid,k); else return query(R[x],R[y],R[lca],R[falca],mid+1,r,k-s); } int id[maxn],rid[maxn],fa[maxn],son[maxn],top[maxn],siz[maxn],dep[maxn],cnt; void dfs1(int u,int f,int d) { siz[u]=1;dep[u]=d; id[u]=++cnt;rid[cnt]=u;fa[u]=f; update(T[u],1,nn,T[f],val(u)); for(int i=0;i<p[u].size();i++) { if(p[u][i]==f)continue; dfs1(p[u][i],u,d+1); siz[u]+=siz[p[u][i]]; if(siz[p[u][i]]>siz[son[u]])son[u]=p[u][i]; } } void dfs2(int u,int t) { top[u]=t; if(!son[u])return; dfs2(son[u],t); for(int i=0;i<p[u].size();i++) { if(p[u][i]!=son[u]&&p[u][i]!=fa[u])dfs2(p[u][i],p[u][i]); } } int callca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y])return y; else return x; } int main() { int m,i,j,k,u,v,ans=0,falca,lca; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]); h[i]=a[i]; } sort(h+1,h+1+n); nn=unique(h+1,h+1+n)-h-1; for(i=1;i<n;i++) { scanf("%d%d",&u,&v); p[u].push_back(v); p[v].push_back(u); } build(T[0],1,nn); siz[0]=0;sum[0]=0; dfs1(1,0,1); dfs2(1,1); while(m--) { scanf("%d%d%d",&u,&v,&k); u^=ans; lca=callca(u,v); falca=fa[lca]; ans=query(T[u],T[v],T[lca],T[falca],1,nn,k); ans=h[ans]; printf("%d ",ans); } }
2019-09-29 22:38:36
静态主席树
感觉hdu2665可以用划分树做 但是划分树之前看过还没好好好好学
等这次主席树学得差不多 再回去看看划分树，试试能不能用划分树做
静态主席树第一题 hdu2665 or 洛谷P3834 求静态第k小
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+50; //求静态区间第k小 //sum[] 需要根据题意来修改 不是主席树自带 int a[maxn],h[maxn]; //a是原序列 h是离散后的序列 int T[maxn],L[maxn*20],R[maxn*20],sum[maxn*20]; /* T[i] 是第i颗线段树的根节点编号 L[i] 是节点i的左节点编号 R[i] 是节点i的右节点编号 sum[i] 是节点i对应区间 数 的 个数 */ int tot; //rt tot是节点编号 //建空树 build(T[0],1,n); // T[0]=1; void build(int& rt,int l,int r) { rt=++tot; sum[rt]=0; if(l==r)return; int mid=(l+r)>>1; build(L[rt],l,mid); build(R[rt],mid+1,r); } //更新rt(T[i]) pre=T[i-1] void update(int &rt,int l,int r,int pre,int x) { rt=++tot; L[rt]=L[pre]; R[rt]=R[pre]; sum[rt]=sum[pre]+1;//添加一个数 sum值比前驱线段树+1 if(l==r)return ; int mid=(l+r)>>1; //节点复用体现在这个if else语句 //只新建包含x的区间节点 if(x<=mid)update(L[rt],l,mid,L[pre],x); else update(R[rt],mid+1,r,R[pre],x); } int query(int s,int e,int l,int r,int k) { if(l==r)return l; int mid=(l+r)>>1; int res=sum[L[e]]-sum[L[s]]; if(k<=res)return query(L[s],L[e],l,mid,k); else return query(R[s],R[e],mid+1,r,k-res); } int main() { int tt; scanf("%d",&tt); while(tt--) { int n,m,i,s,t,k,nn,ans; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&a[i]);h[i]=a[i]; } sort(h+1,h+n+1); nn=unique(h+1,h+1+n)-h-1; tot=0; build(T[0],1,nn); for(i=1;i<=n;i++) update(T[i],1,nn,T[i-1],lower_bound(h+1,h+1+nn,a[i])-h); //因为是[1,nn] 不是[0,nn] 所以是-h 不是-(h+1) while(m--) { scanf("%d%d%d",&s,&t,&k); ans=query(T[s-1],T[t],1,nn,k); printf("%d ",h[ans]); } } }
2019-09-11 09:51:44
(可持久化线段树和主席树一样吗？...
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+50; int a[maxn]; int T[maxn],L[maxn*25],R[maxn*25],val[maxn*25]; /* T[i] 是第i颗线段树的根节点编号 L[i] 是节点i的左节点编号 R[i] 是节点i的右节点编号 */ int tot; //rt tot是节点编号 void build(int&rt,int l,int r) { rt=++tot; if(l==r) { val[rt]=a[l];return; } int mid=(l+r)>>1; build(L[rt],l,mid); build(R[rt],mid+1,r); } int update(int&rt,int l,int r,int pre,int id,int x,int op) { rt=++tot; if(l==r) { if(op==1)val[rt]=x; else val[rt]=val[pre]; return val[rt]; } L[rt]=L[pre]; R[rt]=R[pre]; int mid=(l+r)>>1; if(id<=mid)return update(L[rt],l,mid,L[pre],id,x,op); else return update(R[rt],mid+1,r,R[pre],id,x,op); } /* int getval(int rt,int l,int r,int id) { if(l==r) { return val[rt]; } int mid=(l+r)>>1; if(id<=mid)return getval(L[rt],l,mid,id); else return getval(R[rt],mid+1,r,id); } void show(int v,int n) { printf("%d: ",v); for(int i=1;i<=n;i++)printf("%d ",getval(T[v],1,n,i)); printf(" "); } */ int main() { int n,m,i,v,op,id,vv; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&a[i]); tot=0; build(T[0],1,n);//show(0,n); for(i=1;i<=m;i++) { scanf("%d%d%d",&v,&op,&id); if(op==1) { scanf("%d",&vv); update(T[i],1,n,T[v],id,vv,1); } else { printf("%d ",update(T[i],1,n,T[v],id,0,2)); } //show(i,n); } }
然后是 可持久化并查集
为此昨晚先去学习了按秩合并的并查集(到现在才知道有这个....)
//按秩合并 hdu1232 畅通工程 //http://acm.hdu.edu.cn/showproblem.php?pid=1232 #include<bits/stdc++.h> using namespace std; const int maxn=1e3+50; int pre[maxn],rank[maxn]; inline int find(int x) { int r=x,t; while(x!=pre[x])x=pre[x]; while(r!=x){ t=pre[r]; pre[r]=x; r=t; } return x; } inline void unio(int a,int b) { int fa=find(a); int fb=find(b); if(rank[fa]<=rank[fb]) { pre[fa]=fb; if(rank[fa]==rank[fb])rank[fb]++; } else pre[fb]=fa; } int main() { int n,m,i,j,k,a,b,fa,fb; while(~scanf("%d",&n)) { if(!n)break; scanf("%d",&m); for(i=1;i<=n;i++)pre[i]=i,rank[i]=1; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); unio(a,b); } int ans=0; for(i=1;i<=n;i++) { if(pre[i]==i)ans++; } printf("%d ",ans-1); } }
然后今天有精神了终于看着题解(...)做出了 洛谷P3402 可持久化并查集
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; const int maxn=1e5+50; int n,tot; int pre[maxn*40],dep[maxn*40]; int T[maxn],L[maxn*40],R[maxn*40]; inline void build(int&rt,int l,int r) { rt=++tot; if(l==r) { pre[rt]=l; dep[rt]=1; return ; } int mid=(l+r)>>1; build(L[rt],l,mid); build(R[rt],mid+1,r); } inline int query(int rt,int l,int r,int id) { if(l==r)return rt; int mid=(l+r)>>1; if(id<=mid)return query(L[rt],l,mid,id); else return query(R[rt],mid+1,r,id); } inline void update(int&rt,int l,int r,int past,int id,int val) { rt=++tot; L[rt]=L[past];R[rt]=R[past]; if(l==r) { pre[rt]=val; dep[rt]=dep[past]; return ; } int mid=(l+r)>>1; if(id<=mid)update(L[rt],l,mid,L[past],id,val); else update(R[rt],mid+1,r,R[past],id,val); } inline int find(int rt,int id) { int pnum=query(rt,1,n,id); if(pre[pnum]==id)return pnum; return find(rt,pre[pnum]); } inline void unio(int id,int a,int b)// id T[id] a是数值 fa是点标 { int fa=find(T[id-1],a); int fb=find(T[id-1],b); if(dep[fa]<=dep[fb]) { //pre[fa]=fb; update(T[id],1,n,T[id-1],pre[fa],pre[fb]);//change faid[fa] rt to fb if(dep[fa]==dep[fb])dep[fb]++; } else { //pre[fb]=fa; update(T[id],1,n,T[id-1],pre[fb],pre[fa]); } } int main() { int m,i,j,k,id,op,a,b,fa,fb; scanf("%d%d",&n,&m); tot=0; build(T[0],1,n); for(i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { scanf("%d%d",&a,&b); unio(i,a,b); } else if(op==2) { scanf("%d",&k); T[i]=T[k]; } else if(op==3) { scanf("%d%d",&a,&b); fa=find(T[i-1],a); fb=find(T[i-1],b); T[i]=T[i-1]; if(fa==fb)puts("1"); else puts("0"); // printf("##%d %d ",pre[fa],pre[fb]); } } }
2019-09-12 11:26:43