17我们一起做网站,西安做网站优化,企业宣传片背景音乐,中国建筑装饰装修和主席树类似#xff0c;开一个 rot[N] 数组记录每个版本的根结点即可
int root, idx; // 分别表示根结点编号和当前用到哪个结点
int val[N * 70]; // 结点权值
int pri[N * 70]; // 结点优先级
int sz[N * 70]; // 结点子树大小
int ch[N * 70][2]; // 结点左右儿子
int ta…和主席树类似开一个 rot[N] 数组记录每个版本的根结点即可
int root, idx; // 分别表示根结点编号和当前用到哪个结点
int val[N * 70]; // 结点权值
int pri[N * 70]; // 结点优先级
int sz[N * 70]; // 结点子树大小
int ch[N * 70][2]; // 结点左右儿子
int tag[N * 70]; // 标记
int rot[N]; // 根结点
int sum[N * 70]; // 子段和void getnode(int x) // 创建权值为x的新结点
{sz[ idx] 1;ch[idx][0] ch[idx][1] 0;val[idx] x;tag[idx] 0;sum[idx] x;pri[idx] rand(); // 优先值取随机数保证树形状随机
}void copynode(int x, int y) // 把结点y的信息复制给x
{val[x] val[y];pri[x] pri[y];sz[x] sz[y];ch[x][0] ch[y][0];ch[x][1] ch[y][1];tag[x] tag[y];sum[x] sum[y];
}void pushup(int u) // 更新结点u信息
{sz[u] sz[ch[u][0]] sz[ch[u][1]] 1;sum[u] sum[ch[u][0]] sum[ch[u][1]] val[u];
}void pushdown(int u) // 懒标记下传
{if (tag[u]){int p;if (ch[u][0]){p idx;copynode(p, ch[u][0]);ch[u][0] p;}if (ch[u][1]){p idx;copynode(p, ch[u][1]);ch[u][1] p;}swap(ch[u][0], ch[u][1]);if (ch[u][0]) tag[ch[u][0]] ^ 1;if (ch[u][1]) tag[ch[u][1]] ^ 1;tag[u] 0;}
}void split(int u, int x, int lt, int rt) // 把treap分成小于等于x和大于x的两个部分
{if (u 0){lt rt 0;return;}pushdown(u);if (sz[ch[u][0]] 1 x) // 当前点小于x说明分界点在右儿子{lt idx;copynode(lt, u);split(ch[lt][1], x - (sz[ch[u][0]] 1), ch[lt][1], rt);pushup(lt);}else // 当前点大于x说明分界点在左儿子{rt idx;copynode(rt, u);split(ch[rt][0], x, lt, ch[rt][0]);pushup(rt);}
}int merge(int lt, int rt) // 合并根结点编号为lt和rt的两棵treap
{if (lt 0 || rt 0) return lt rt;if (pri[lt] pri[rt]) // lt的优先级比rt大 就把rt合并到lt的右子树{pushdown(lt);ch[lt][1] merge(ch[lt][1], rt);pushup(lt);return lt;}else // rt的优先级比lt大 就把lt合并到rt的左子树{pushdown(rt);ch[rt][0] merge(lt, ch[rt][0]);pushup(rt);return rt;}
}void insert(int rot, int p, int x) // 将权值为x的新结点插入根结点为rot的treap
{int lt, rt;split(rot, p, lt, rt); // 先把原treap分成小于等于x和大于x两个部分getnode(x); // 创建值为x的结点rot merge(merge(lt, idx), rt); // 先合并小于等于x的子树和新结点 再将其与大于x的子树合并return;
}void del(int rot, int x)
{int lt, md, rt;split(rot, x, lt, rt); // 先把原treap分成小于等于x和大于x两个部分split(lt, x - 1, lt, md); // 再把小于等于x的部分分成小于等于x-1和大于x-1两个部分// 此时以md为根结点的子树内所有结点的权值都是xmd merge(ch[md][0], ch[md][1]); // 合并md的左右儿子 即删去md这个结点rot merge(lt, rt); // 先合并小于等于x-1的部分和等于x的部分 再将其与大于x的子树合并return;
}
