平衡树(无旋转)
替罪羊树
是比较优雅的暴力(想到了莫队)。
根据定义的alpha等参数来判断树是否需要重构。重构的时候，先中序遍历得到序列，然后利用分治的思想，每次拎起中间的点作为当前子树的根节点，然后递归处理这个点左右两端的序列。
每次插入均摊到的复杂度是$O(log(size(T)))$
2020.11.26
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int MAXN = 1e5+5;
const double alpha = 0.75;//平衡因子
struct Node{
int l,r,val;
int size,fact;//子树大小,子树内存在的节点数
bool exist;//是否存在
}tzy[MAXN];
int cnt,root;//节点堆计数,根节点下标
void newnode(int &now,int val){//新建节点
now = ++cnt;
tzy[now].val=val;
tzy[now].size=tzy[now].fact = 1;//初始化
tzy[now].exist = 1;
}
bool imbalance(int now){//判断平衡
//如果左右子树中的一个重量占比超过平衡因子,或者子树中假的点超过30%
if(max(tzy[tzy[now].l].size,tzy[tzy[now].r].size)>tzy[now].size*alpha
||tzy[now].size-tzy[now].fact>tzy[now].size*0.3)
return 1;
else return 0;
}
vector<int> v;
void ldr(int now){//中序遍历
if(!now) return;//到底了
ldr(tzy[now].l);
if(tzy[now].exist) v.push_back(now);//存在的点拎起来,不存在的丢掉
ldr(tzy[now].r);
}
void lift(int l,int r,int &now){//递归分治把中间的点拎起来
if(l==r){
now = v[l];
tzy[now].l=tzy[now].r = 0;//叶子节点
tzy[now].size=tzy[now].fact = 1;
return;
}
int m = (l+r)>>1;//找到中间节点;
//特殊情况,如果是x 5 5 x x的话,相同的值本应该放在右边,这里却放到了左边
while(l<m&&tzy[v[m]].val==tzy[v[m-1]].val)//左移,直到找到合适的点
m--;
now = v[m];//找到应该被拎起来的点
//分治思想
if(l<m) lift(l,m-1,tzy[now].l);//左边还有可以拎起来的,最后一个参数是为了把树接起来的
else tzy[now].l = 0;
lift(m+1,r,tzy[now].r);//右边一定有可以拎起来的
tzy[now].size = tzy[tzy[now].l].size+tzy[tzy[now].r].size+1;
tzy[now].fact = tzy[tzy[now].l].fact+tzy[tzy[now].r].fact+1;
}
void rebuild(int &now){//之前这里now忘了写引用
v.clear();
ldr(now);//得到中序遍历序列
if(v.empty()){//所有的都是被假的点,特判
now = 0;
return;
}
lift(0,v.size()-1,now);
}
void update(int now,int end){//因为没有记录父亲的编号,所以只能头递归
if(!now) return;
if(tzy[end].val<tzy[now].val) update(tzy[now].l,end);
else update(tzy[now].r,end);
tzy[now].size=tzy[tzy[now].l].size+tzy[tzy[now].r].size+1;
}
void check(int &now,int end){//沿路径检查
if(now==end) return;
if(imbalance(now)){
rebuild(now);//重构
update(root,now);//重构后更新
return;
}
if(tzy[end].val<tzy[now].val) check(tzy[now].l,end);
else check(tzy[now].r,end);
}
void ins(int &now,int val){//递归插入节点
if(!now){//now=0是没有节点的地方(空儿子)
newnode(now,val);
check(root,now);//检查插入后是否需要重构
return;
}
tzy[now].size++;
tzy[now].fact++;
if(val<tzy[now].val) ins(tzy[now].l,val);
else ins(tzy[now].r,val);
}
void del(int now,int val){
if(tzy[now].exist&&tzy[now].val==val){//找到要删的了
tzy[now].exist = 0;
tzy[now].fact--;
check(root,now);//检查删除后是否需要重构
return;
}
tzy[now].fact--;//路径上的节点的fact都需要更新
//这里是因为数据没有删除"不存在的点"的情况,所以可以这样写
if(val<tzy[now].val) del(tzy[now].l,val);
else del(tzy[now].r,val);
}
int getrank(int val){//查询第几大
int now = root,rank = 1;
while(now){
if(val<=tzy[now].val) now = tzy[now].l;
else{
rank+=tzy[now].exist+tzy[tzy[now].l].fact;//加上当前点和左子树
now = tzy[now].r;
}
}
return rank;
}
int getnum(int rank){//查询第k小
int now = root;
while(now){
if(tzy[now].exist&&tzy[now].exist+tzy[tzy[now].l].fact==rank) break;//找到
else if(tzy[tzy[now].l].fact>=rank)
now = tzy[now].l;
else{
rank-=tzy[now].exist+tzy[tzy[now].l].fact;//左子树没有去边找
now = tzy[now].r;
}
}
return tzy[now].val;
}
void solve(){
int typ,hc;
cin>>typ;
if(typ==1){//插入
cin>>hc;
ins(root,hc);
}
else if(typ==2){//删除
cin>>hc;
del(root,hc);
}
else if(typ==3){//查询x的排名
cin>>hc;
cout<<getrank(hc)<<endl;
}
else if(typ==4){//查询排名为x的数
cin>>hc;
cout<<getnum(hc)<<endl;
}
else if(typ==5){//前驱
cin>>hc;
cout<<getnum(getrank(hc)-1)<<endl;
//注意前驱和后继查询的区别,理一下逻辑其实很简单
}
else if(typ==6){//后继
cin>>hc;
cout<<getnum(getrank(hc+1))<<endl;
//我一开始写的是getnum(getrank(hc)+1)
//如果hc不在树里,就会出错
}
}
int main(){
int t;
cin>>t;
while(t--) solve();
}
//我之前的一个疑问,tzy树有0这个假的点作为根,如果从root=0这个点重构了,root没了该怎么办
//后来想了想,在重构里now用的是引用,所以引用root的时候,重构时root会被改变
//即一开始root是一个val=0的假点,在root子树重构之后,root会被替换成一个真点
//洛谷 P3369 【模板】普通平衡树
//https://www.luogu.com.cn/problem/P3369范浩强Treap
常数略大，因为有随机所以可以防毒瘤数据卡。
数据结构同时对节点的val维护平衡树性质，对节点的key(一个随机数值)则是维护大根堆的性质。每次操作对树进行分裂，传入参数val，分出一颗x小于等于val，另一颗y大于等于val。合并时要兼顾平衡树和大根堆的性质。
范浩强Treap的期望深度是$O(log(size(T)))$的。
2020.11.29
#include<iostream>
#include<ctime>
#include<random>
using namespace std;
const int MAXN = 1e5+5;
struct Node{
int l,r;
int val,key;//val维护平衡树,key维护大根堆
int size;
}fhq[MAXN];
int cnt,root;
mt19937 rnd(233);//产生速度快,周期大的高质量随机数
inline int newnode(int val){
fhq[++cnt].val = val;
fhq[cnt].key = rnd();
fhq[cnt].size = 1;
return cnt;//返回编号
}
inline void update(int now){//更新大小
fhq[now].size = fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}
void split(int now,int val,int &x,int &y){//树分裂,通过传引用告诉函数应该接在哪里
//x是x树的"接口",y是y树的"接口" : 分裂后x树的值<=val,y树>val
if(!now){x=y=0;return;}
if(fhq[now].val<=val){
x = now;
//左子树都比val小,直接把当前节点连带左子树接到x上,下一步继续去右子树找
split(fhq[now].r,val,fhq[now].r,y);//x的接口变成r位置,y的接口不变
}
else{
y = now;
split(fhq[now].l,val,x,fhq[now].l);
}
update(now);
}
int merge(int x,int y){//传入时保证x树中的val全部小于y树!
if(!x||!y) return x+y;//如果有一方为0,返回另一方
if(fhq[x].key>fhq[y].key){//维护key大根堆的性质,根一定比儿子大
fhq[x].r = merge(fhq[x].r,y);//y的val比x大,所以放右边
update(x);
return x;//返回值是和上一层接起来
}
else{
fhq[y].l = merge(x,fhq[y].l);
update(y);
return y;
}
}
int x,y,z;//因为之后会经常用到所以这里先定义
inline void ins(int val){
//按val分xz树,新节点y,合并xy,再和z合并
split(root,val,x,y);
root = merge(merge(x,newnode(val)),y);//第一次插入的点也会在这里被变成root,所以不用担心
}
inline void del(int val){
//1.按val分成xz,按val-1把x分成xy 2.删掉y树的根(只删去一个val) 3.合并xyz
split(root,val,x,z);
split(x,val-1,x,y);
y = merge(fhq[y].l,fhq[y].r);
root = merge(merge(x,y),z);
}
inline int getrank(int val){
//按照val-1分xy,x的大小+1即val排名
split(root,val-1,x,y);
int res = fhq[x].size+1;
root = merge(x,y);
return res;
}
inline int getnum(int rank){//普普通通找数字
int now = root;
while(now){//询问rank有可能大于总结点数量,这时候会返回0
if(fhq[fhq[now].l].size+1==rank)break;
else if(fhq[fhq[now].l].size>=rank) now=fhq[now].l;
else{
rank-=fhq[fhq[now].l].size+1;
now = fhq[now].r;
}
}
return fhq[now].val;
}
inline int pre(int val){
//按val-1分xy,找x中最大的点
split(root,val-1,x,y);
int now = x;
while(fhq[now].r) now = fhq[now].r;//一直往右边找
int res = fhq[now].val;
merge(x,y);
return res;
}
inline int nxt(int val){
split(root,val,x,y);
int now = y;
while(fhq[now].l) now = fhq[now].l;
int res = fhq[now].val;
merge(x,y);
return res;
}
int main(){
int t,typ,x;
cin>>t;
while(t--){
cin>>typ>>x;
if(typ==1) ins(x);
else if(typ==2) del(x);
else if(typ==3) cout<<getrank(x)<<endl;
else if(typ==4) cout<<getnum(x)<<endl;
else if(typ==5) cout<<pre(x)<<endl;
else if(typ==6) cout<<nxt(x)<<endl;
}
}
//同样思考了一下root初始值的事情,一开始的root是无效值0,这时候是不会执行split的
//在插入第一个数值后,root就变成了这个新的节点
//洛谷 P3369 【模板】普通平衡树
//https://www.luogu.com.cn/problem/P3369文艺平衡树
文艺平衡树是fhq_treap处理序列上问题(区间操作)的一个例子,进行区间操作一般是用这种通过节点个数进行分裂的split,这里与其他平衡树查询第k大的操作类似。而通过懒惰标记处理旋转区间的操作又与线段树比较相似。
对于有懒惰标记的点u进行pushdown时，交换左右儿子，并给左右儿子都打上懒惰标记。（妙啊）
洛谷的这道板子题是保证了是123456这样的的序列，第一是无需ins直接用merge(root,i)来插入,因为i一定比之前出现的数值都大,如果没有这种条件,应该也可以另外建一个数组通过下标来映射数值,或者给Node多加一个参数存实际值。
#include<iostream>
#include<ctime>
#include<vector>
#include<random>
using namespace std;
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
const int MAXN = 1e5+5;
struct Node{
int l,r;
int val,key;
int size;
bool reverse;//旋转的懒惰标记
}fhq[MAXN];
int cnt,root;
mt19937 rnd(233);
vector<int>res;//因为行的末尾不能有空格所以我先用一个vector存着
inline int newnode(int val){
fhq[++cnt].val = val;
fhq[cnt].key = rnd();
fhq[cnt].size=1;
return cnt;
}
inline void update(int now){
fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size+1;
}
inline void pushdown(int now){
//如果当前节点的儿子有可能之后被动到,就需要向下传递reverse
swap(fhq[now].l,fhq[now].r);
fhq[fhq[now].l].reverse^=1;//儿子的懒惰标记0变1,1变0
fhq[fhq[now].r].reverse^=1;
fhq[now].reverse = 0;//之前疑惑这里为什么不用取反^1的
//其实是因为如果now没有标记reverse,就不用执行pushdown
}
void split(int now,int siz,int &x,int &y){//按照大小分裂
//有点类似取第k大getnum的操作
if(!now){x=y=0;return;}
if(fhq[now].reverse) pushdown(now);//之后分裂操作可能碰到儿子,所以要pushdown
if(fhq[fhq[now].l].size<siz){
x = now;
split(fhq[now].r,siz-fhq[fhq[now].l].size-1,fhq[now].r,y);
}
else{
y = now;
split(fhq[now].l,siz,x,fhq[now].l);
}
update(now);
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(fhq[x].key<fhq[y].key){//这里其实用什么符号都行
if(fhq[x].reverse) pushdown(x);
fhq[x].r = merge(fhq[x].r,y);
update(x);
return x;
}
else{
if(fhq[y].reverse) pushdown(y);
fhq[y].l = merge(x,fhq[y].l);
update(y);
return y;
}
}
void reverse(int l,int r){//区间反转
//拆成三段,(1,l-1),(l,r),(r+1,n);
int x,y,z;
split(root,l-1,x,y);
split(y,r-l+1,y,z);
fhq[y].reverse^=1;
root=merge(merge(x,y),z);
}
void ldr(int now){//最后用中序遍历找到结果
if(!now) return;
if(fhq[now].reverse) pushdown(now);
ldr(fhq[now].l);
res.push_back(fhq[now].val);//推入结果的序列
ldr(fhq[now].r);
}
int main(){
int n,m;
cin>>n>>m;
rep(i,1,n) root = merge(root,newnode(i));//因为i一定比之前出现的都大才可以这样
int l,r;
while(m--){
cin>>l>>r;
reverse(l,r);
}
res.clear();
ldr(root);
int siz = res.size();
rep(i,0,siz-1){
cout<<res[i];
if(i!=siz-1) cout<<' ';
}
cout<<endl;
}
//AgOH说,平衡树也是可以处理序列(区间操作)问题的,一般使用的split都是这种按个数siz分裂的split
//这题里面有点线段树的味道,通过一个懒惰标记节省了很多没有必要的反转消耗的时间
//洛谷P3391 【模板】文艺平衡树
//https://www.luogu.com.cn/problem/P3391其他
树上启发式合并
用于没有修改只有查询的树形问题，且询问以所有节点为根子树（即对每个节点为根的子树都要询问）
第一遍dfs(init函数)先处理出每个节点的重儿子，第二遍dfs利用头递归处理轻儿子的信息得到子树上的答案，重儿子的信息在cnt里从儿子传给爸爸一直网上传，但他的爸爸不一定是爷爷的重儿子，所以这个dfs有一个opt参数，如果不是则opt=0要清空这颗子树的贡献。
用可以选择参数的dfs1函数，val=1时是加上轻儿子的贡献，=-1时删去轻儿子的贡献。
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int MAXN = 1e5+5;
const int MAXM = 1e5+5;
int sz[MAXN],son[MAXN];//子树大小和重儿子
//int ans[MAXN];//存最多的颜色和编号和,这题没必要
int c[MAXN];//每个点的颜色
int cnt[MAXM];//存每种颜色的点数
ll bhh[MAXN],bsum;//题目要求颜色的编号和
int maxx;//临时变量,用来找最大颜色数量的
int n;
vector<int> e[MAXN];
void init(int now,int pre){//预处理找重儿子
sz[now] = 1;son[now] = -1;
for(auto v:e[now]){
if(v==pre) continue;
init(v,now);
sz[now]+=sz[v];
if(son[now]==-1||sz[v]>sz[son[now]]) son[now]=v;
}
}
void dfs1(int now,int pre,int val,int rt){//rt是dfs里面当前在统计的子树根
//val=1的时候加上子节点的贡献,而-1时是dfs里面opt=1(代表轻儿子)时删去贡献
cnt[c[now]]+=val;
if(val==1){
if(cnt[c[now]]>maxx) maxx=cnt[c[now]],bsum=c[now];
else if(cnt[c[now]]==maxx) bsum+=c[now];
}
//遍历子节点的时候看到什么颜色就检查这个颜色
for(auto v:e[now]) if(v!=pre)dfs1(v,now,val,rt);
}
void dfs(int now,int pre,int opt){//opt为1代表要清空
for(auto v:e[now]){
if(v!=son[now]&&v!=pre) dfs(v,now,1);//先轻儿子,需要删去
}
if(son[now]!=-1) dfs(son[now],now,0);//处理重儿子
//此时计算轻儿子的贡献,重儿子的在cnt里面祖传上来了
for(auto v:e[now]){
if(v!=pre&&v!=son[now]) dfs1(v,now,1,now);//统计轻儿子上的结果
}
cnt[c[now]]++;//也要加上当前节点
if(cnt[c[now]]>maxx) maxx=cnt[c[now]],bsum=c[now];
//这里我一开始用的cnt[c[now]]>cnt[ans[now]],但是c[now]和ans[rt]相同时出问题
else if(cnt[c[now]]==maxx) bsum+=c[now];
bhh[now] = bsum;//记录结果
//减去轻儿子的贡献
if(opt){
cnt[c[now]]--;
for(auto v:e[now])
if(v!=pre) dfs1(v,now,-1,now);
maxx = bsum = 0;//删去轻儿子这颗子树对bsum和maxx的贡献
}
}
int rt = 1;//题目默认1为根节点
int main(){
cin>>n;
rep(i,1,n) cin>>c[i];
int u,v;
rep(i,1,n-1){
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
init(rt,-1);
dfs(rt,-1,1);
rep(i,1,n){
cout<<bhh[i];
if(i!=n) cout<<' ';
}
cout<<endl;
}
//没有修改只有查询的树形问题
//且询问以所有节点为根子树（即对每个节点为根的子树都要询问）。
//洛谷CF600E Lomsat gelral
//https://www.luogu.com.cn/problem/CF600E树形DP
树上背包
每个节点要做一次背包，父节点有p个儿子节点时，每个儿子节点看作一组物品每组m个(儿子dp的时候的结果)，做分组背包即可。
状态转移方程为：$dp[x][i]=max(dp[son_i][j])+score(x)$。j从1到容量m，表示这组里选j个。
#include<iostream>
#include<cstring>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
int cansel_sync =(ios::sync_with_stdio(0),cin.tie(0),0);
const int MAXN = 333;
struct Node{
int v,nxt;//next同一个父亲的下一个点
int w;//权值,这题用不到
}edges[MAXN];
int head[MAXN];//记录u为起点的第一条边编号
int cnt;//总边数
int minn;
inline void add(int u,int v){//增加边
edges[++cnt] = Node{v,head[u]};
head[u]=cnt;
}
int n,m;
int dp[MAXN][MAXN],val[MAXN];
void dfs(int now){
dp[now][1] = val[now];//肯定要选定自己
for(int i = head[now];i!=-1;i=edges[i].nxt){
int v = edges[i].v;
dfs(v);
//分组背包
repb(j,m,1){//当前u背包容量
rep(k,0,j-1){//从v儿子里拿几个
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[v][k]);
//状态转移
}
}
}
}
int main(){
while(cin>>n>>m&&m&&n){
memset(head,-1,sizeof(head));
memset(dp,0,sizeof(dp));
cnt = 0;
int fa;//fa表示依赖的点
rep(i,1,n){
cin>>fa>>val[i];
add(fa,i);
}
m++;//因为之后的dp[0][m]算上了0点,所以要+1
val[0]=0;//构造虚节点0
dfs(0);
cout<<dp[0][m]<<endl;
}
}
//洛谷P2014 [CTSC1997]选课
//https://www.luogu.com.cn/problem/P2014
