目录
A - 文艺平衡树
这里的Splay维护是按照的是序列中的编号排序
那么，继续考虑，其实最终的结果也就是整颗Splay的中序遍历（平衡树的性质诶）
那么，现在如果按照权值来维护显然是不正确的
继续找找规律，发现，如果一个点在序列中的位置为第K个
那么，他就是平衡树的第K大（就当做普通的Splay来看的话）
所以，序列中的位置就变成了区间的第K大点
继续考虑如何翻转
翻转也就是整颗子树的每一个节点的左右儿子交换
因此，只要在根节点的地方打一个标记
在旋转之前下方一下标记就行了
最后输出的时候输出的就是Splay的中序遍历
至于初始的Splay怎么建立，可以直接构造完美的Splay
像我这种比较懒得，直接弄了一个insert。。。
-
#include<iostream>
-
#include<cstdio>
-
#include<cstdlib>
-
#include<cstring>
-
#include<cmath>
-
#include<algorithm>
-
using
namespace std;
-
#define MAX 200000
-
inline int read()
-
{
-
int x=
0,t=
1;
char ch=
getchar();
-
while((ch<
'0'||ch>
'9')&&ch!=
'-')ch=
getchar();
-
if(ch==
'-')t=
-1,ch=
getchar();
-
while(ch<=
'9'&&ch>=
'0')x=x*
10+ch
-48,ch=
getchar();
-
return x*t;
-
}
-
struct
Node
-
{
-
int ch[
2];
-
int ff,v;
-
int size;
-
int mark;
-
void init(int x,int fa)
-
{
-
ff=ch[
0]=ch[
1]=
0;
-
size=
1;v=x;ff=fa;
-
}
-
}t[MAX];
-
int N,root,M,tot;
-
inline void pushup(int x)
-
{
-
t[x].size=t[t[x].ch[
0]].size+t[t[x].ch[
1]].size+
1;
-
}
-
inline void pushdown(int x)
-
{
-
if(t[x].mark)
-
{
-
t[t[x].ch[
0]].mark^=
1;
-
t[t[x].ch[
1]].mark^=
1;
-
t[x].mark=
0;
-
swap(t[x].ch[
0],t[x].ch[
1]);
-
}
-
}
-
inline void rotate(int x)
-
{
-
int y=t[x].ff;
-
int z=t[y].ff;
-
int k=t[y].ch[
1]==x;
-
t[z].ch[t[z].ch[
1]==y]=x;
-
t[x].ff=z;
-
t[y].ch[k]=t[x].ch[k^
1];
-
t[t[x].ch[k^
1]].ff=y;
-
t[x].ch[k^
1]=y;
-
t[y].ff=x;
-
pushup(y);
pushup(x);
-
}
-
inline void Splay(int x,int goal)
-
{
-
while(t[x].ff!=goal)
-
{
-
int y=t[x].ff;
int z=t[y].ff;
-
if(z!=goal)
-
(t[z].ch[
1]==y)^(t[y].ch[
1]==x)?
rotate(x):
rotate(y);
-
rotate(x);
-
}
-
if(goal==
0)root=x;
-
}
-
inline void insert(int x)
-
{
-
int u=root,ff=
0;
-
while(u)ff=u,u=t[u].ch[x>t[u].v];
-
u=++tot;
-
if(ff)t[ff].ch[x>t[ff].v]=u;
-
t[u].
init(x,ff);
-
Splay(u,
0);
-
}
-
inline int Kth(int k)
-
{
-
int u=root;
-
while(
233)
-
{
-
pushdown(u);
-
if(t[t[u].ch[
0]].size>=k)u=t[u].ch[
0];
-
else
if(t[t[u].ch[
0]].size+
1==k)
return u;
-
else k-=t[t[u].ch[
0]].size+
1,u=t[u].ch[
1];
-
}
-
}
-
void write(int u)
-
{
-
pushdown(u);
-
if(t[u].ch[
0])
write(t[u].ch[
0]);
-
if(t[u].v>
1&&t[u].v<N+
2)
printf(
"%d ",t[u].v
-1);
-
if(t[u].ch[
1])
write(t[u].ch[
1]);
-
}
-
inline void Work(int l,int r)
-
{
-
l=
Kth(l);
-
r=
Kth(r+
2);
-
Splay(l,
0);
-
Splay(r,l);
-
t[t[t[root].ch[
1]].ch[
0]].mark^=
1;
-
}
-
int main()
-
{
-
N=
read();M=
read();
-
for(
int i=
1;i<=N+
2;++i)
insert(i);
-
while(M--)
-
{
-
int l=
read(),r=
read();
-
Work(l,r);
-
}
-
write(root);
-
printf(
"\n");
-
return
0;
-
}
B - 可持久化文艺平衡树
FHQ Treap其实是一种加强版的Treap。与一般的Treap树不同，FHQ Treap不依赖旋转操作保持自身结构的平衡，而是依赖分裂和合并操作维持树的平衡性质。
我们先来介绍一下关键操作:
代码如下
-
#include<cstdio>
-
#include<cstring>
-
#include<cmath>
-
#include<climits>
-
#include<cstdlib>
-
#include<ctime>
-
#include<algorithm>
-
#include<complex>
-
#include<iostream>
-
#include<map>
-
#include<queue>
-
#include<vector>
-
#define ll long long
-
#define INF 0x3f3f3f3f
-
#define ls(p) tree[p].lson
-
#define rs(p) tree[p].rson
-
#define tls(p) tree[ls(p)]
-
#define trs(p) tree[rs(p)]
-
#define t(p) tree[p]
-
#define tpi t(++tot)
-
#define tp t(tot)
-
using
namespace std;
-
const int N(2e5);
-
int n;ll lastans;
-
struct
node
-
{
-
int rand,size,tag;
-
ll val,sum;
-
int lson,rson;
-
}tree[(N<<
7)+
10];
-
int rt[N+
10];
-
inline int new_node(long long v=0)
-
{
-
static int tot(0);
-
tpi.val=v;tp.sum=v;
-
tp.rand=
rand();tp.size=
1;
-
return tot;
-
}
-
inline int copy_node(int p)
-
{
-
int ret=
new_node();
-
tree[ret]=tree[p];
-
return ret;
-
}
-
inline void push_up(int p)
-
{
-
tree[p].size=
tls(p).size+
trs(p).size+
1;
-
tree[p].sum=
tls(p).sum+
trs(p).sum+
t(p).val;
-
}
-
inline void push_down(int p)
-
{
-
if(!
t(p).tag)
return;
-
if(
ls(p))
ls(p)=
copy_node(
ls(p));
-
if(
rs(p))
rs(p)=
copy_node(
rs(p));
-
swap(
ls(p),
rs(p));
-
if(
ls(p))
tls(p).tag^=
1;
-
if(
rs(p))
trs(p).tag^=
1;
-
tree[p].tag=
0;
-
}
-
void split(int p,int k,int &x,int &y)
-
{
-
if(!p){x=y=
0;
return;}
-
push_down(p);
-
if(
tls(p).size<k){x=
copy_node(p);
split(
rs(x),k-
tls(p).size
-1,
rs(x),y);
push_up(x);}
-
else{y=
copy_node(p);
split(
ls(y),k,x,
ls(y));
push_up(y);}
-
}
-
int merge(int x,int y)
-
{
-
if(!x||!y)
return x|y;
-
push_down(x);
push_down(y);
-
if(
t(x).rand<
t(y).rand){
rs(x)=
merge(
rs(x),y);
push_up(x);
return x;}
-
else{
ls(y)=
merge(x,
ls(y));
push_up(y);
return y;}
-
}
-
int main()
-
{
-
srand(
224144);
scanf(
"%d",&n);
-
int cnt(0);
int v,op;ll a,b;
int x,y,z;
-
while(n--)
-
{
-
scanf(
"%d%d",&v,&op);
-
if(op==
1)
-
{
-
scanf(
"%lld%lld",&a,&b);
-
a^=lastans;b^=lastans;
-
split(rt[v],a,x,y);
-
rt[++cnt]=
merge(
merge(x,
new_node(b)),y);
-
}
-
if(op==
2)
-
{
-
scanf(
"%lld",&a);
-
a^=lastans;
-
split(rt[v],a,x,z);
-
split(x,a
-1,x,y);
-
rt[++cnt]=
merge(x,z);
-
}
-
if(op==
3)
-
{
-
scanf(
"%lld%lld",&a,&b);
-
a^=lastans;b^=lastans;
-
split(rt[v],b,x,z);
-
split(x,a
-1,x,y);
-
t(y).tag^=
1;
-
rt[++cnt]=
merge(
merge(x,y),z);
-
}
-
if(op==
4)
-
{
-
scanf(
"%lld%lld",&a,&b);
-
a^=lastans;b^=lastans;
-
split(rt[v],b,x,z);
-
split(x,a
-1,x,y);
-
printf(
"%lld\n",lastans=
t(y).sum);
-
rt[++cnt]=
merge(
merge(x,y),z);
-
}
-
}
-
return
0;
-
}
C - 可持久化平衡树
主要思路：FHQ Treap + 可持久化
普通FHQ Treap加上一点可持久化的东西如下：(打上注释的代码是可持久化的特殊操作)
-
#include<iostream>
-
#include<cstdio>
-
#include<cstdlib>
-
#include<cstring>
-
#include<cmath>
-
#include<algorithm>
-
#include<string>
-
#include<vector>
-
#include<set>
-
#include<queue>
-
#include<stack>
-
using
namespace std;
-
#define go(i,j,n,k) for(int i=j;i<=n;i+=k)
-
#define fo(i,j,n,k) for(int i=j;i>=n;i-=k)
-
#define rep(i,x) for(int i=h[x];i;i=e[i].nxt)
-
#define mn 500010
-
#define ld long double
-
#define fi first
-
#define se second
-
#define inf 1<<30
-
#define ll long long
-
#define root 1,n,1
-
#define lson l,m,rt<<1
-
#define rson m+1,r,rt<<1|1
-
#define bson l,r,rt
-
inline ll read(){
-
ll x=
0,f=
1;
char ch=
getchar();
-
while(ch>
'9'||ch<
'0'){
if(ch==
'-')f=-f;ch=
getchar();}
-
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=
getchar();}
-
return x*f;
-
}
-
struct
edge{
-
int ch[
2], sze, pri;
-
ll w;
-
} z[mn *
50];
-
int rot[mn], xx, yy, zz, n, cnt;
-
inline void update(int rt) {
-
z[rt].sze =
1;
-
if(z[rt].ch[
0]) z[rt].sze += z[z[rt].ch[
0]].sze;
-
if(z[rt].ch[
1]) z[rt].sze += z[z[rt].ch[
1]].sze;
-
}
-
inline int newnode(ll w = 0) {
-
z[++cnt].w = w;
-
z[cnt].sze =
1;
-
z[cnt].pri =
rand();
-
return cnt;
-
}
-
inline int merge(int x, int y) {
-
if(!x || !y)
return x + y;
-
if(z[x].pri < z[y].pri) {
-
int rt =
newnode();
-
z[rt] = z[x];
-
z[rt].ch[
1] =
merge(z[rt].ch[
1], y);
-
update(rt);
-
return rt;
-
}
else {
-
int rt =
newnode();
-
z[rt] = z[y];
-
z[rt].ch[
0] =
merge(x, z[rt].ch[
0]);
-
update(rt);
-
return rt;
-
}
-
}
-
inline void split(int rt, ll k, int &x, int &y) {
-
if(!rt) x = y =
0;
-
else {
-
if(z[rt].w <= k) {
-
x =
newnode();
-
z[x] = z[rt];
-
split(z[x].ch[
1], k, z[x].ch[
1], y);
-
update(x);
-
}
else {
-
y =
newnode();
-
z[y] = z[rt];
-
split(z[y].ch[
0], k, x, z[y].ch[
0]);
-
update(y);
-
}
-
}
-
}
-
inline int findkth(int rt, int k) {
-
while(
1119) {
-
if(k <= z[z[rt].ch[
0]].sze)
-
rt = z[rt].ch[
0];
-
else {
-
if(z[rt].ch[
0]) k -= z[z[rt].ch[
0]].sze;
-
if(!--k)
return rt;
-
rt = z[rt].ch[
1];
-
}
-
}
-
}
-
int main(){
-
n =
read();
-
go(i,
1, n,
1) {
-
xx = yy = zz =
0;
-
int tmp =
read(), s =
read(); ll a =
read();
-
rot[i] = rot[tmp];
-
if(s ==
1) {
-
split(rot[i], a, xx, yy);
-
rot[i] =
merge(
merge(xx,
newnode(a)), yy);
-
}
else
if(s ==
2) {
-
split(rot[i], a, xx, zz);
-
split(xx, a -
1, xx, yy);
-
yy =
merge(z[yy].ch[
0], z[yy].ch[
1]);
-
rot[i] =
merge(
merge(xx, yy), zz);
-
}
else
if(s ==
3) {
-
split(rot[i], a -
1, xx, yy);
-
printf(
"%lld\n", z[xx].sze +
1);
-
rot[i] =
merge(xx, yy);
-
}
else
if(s ==
4) {
-
printf(
"%lld\n", z[
findkth(rot[i], a)].w);
-
}
else
if(s ==
5) {
-
split(rot[i], a -
1, xx, yy);
-
if(xx ==
0) {
-
printf(
"-2147483647\n");
-
continue;
-
}
-
printf(
"%lld\n", z[
findkth(xx, z[xx].sze)].w);
-
rot[i] =
merge(xx, yy);
-
}
else
if(s ==
6) {
-
split(rot[i], a, xx, yy);
-
if(yy ==
0) {
-
printf(
"2147483647\n");
-
continue;
-
}
-
printf(
"%lld\n", z[
findkth(yy,
1)].w);
-
rot[i] =
merge(xx, yy);
-
}
-
}
-
return
0;
-
}
D - 维护数列
首先，要有一点splay维护区间操作的基础。
splay维护区间的基本原理，就是将区间[l,r]的端点l-1,和r+1不断的通过伸展操作即splay到根，将l-1伸展到根，将r+1伸展到根的右儿子，那么[l,r]这段区间就在根的右儿子的左儿子上了。
特别要注意的是，==这里的l,r不是给出的区间端点的编号，而是我们在平衡树的中序遍历中区间端点的编号。即在平衡树中排名(rank)为l,r的两个节点的真实编号，而对于l=1或r=n的情况就非常特殊了，我们有两种解决方案，一种就是分类讨论，将这4种情况枚举，然后进行操作，这么做固然可行，但是当操作变多时，会使整个程序显得繁琐，并且难于调试。另一种解决方案就是建立虚拟节点，我们把需要维护的区间全部变成[l+1,r+1]，那么我们虚拟出一个1号节点和一个n+2号节点，那么整个操作就显得十分自然了==。
那么问题就明显是一个splay的基本模板题了。而维护区间翻转，在洛谷的P3391文艺平衡树中有更裸的题目。
这里，一个操作一个操作的解决。
初始化
首先，对于原序列，我们不应该一个一个读入，然后插入，那么效率就是O(nlogn),而splay的常数本身就很大，所以考虑一个优化，就是把原序列一次性读入后，直接类似线段树的build，搞一个整体建树，即不断的将当前点维护的区间进行二分，到达单元素区间后，就把对应的序列值插入进去，这样，我们一开始建的树就是一个非常平衡的树，可以使后续操作的常数更小，并且建树整个复杂度只是O(2n)的。
Insert操作
其次，我们来考虑一下如何维护一个insert操作。我们可以这么做，首先如上将需要insert的区间变成节点数目为tot的平衡树,然后把k+1（注意我们将需要操作的区间右移了一个单位，所以题目所给k就是我们需要操作的k+1）移到根节点的位置，把原树中的k+2移到根节点的右儿子的位置。然后把需要insert的区间，先build成一个平衡树，把需要insert的树的根直接挂到原树中k+1的左儿子上就行了。
Delete操作
再然后，我们来考虑一下delete操作，我们同样的，把需要delete的区间变成[k+1,k+tot]（注意，是删去k后面的tot个数，那么可以发现我们需要操作的原区间是[k,k+tot-1]!），然后把k号节点移到根节点的位置，把k+tot+2移到根节点的右儿子位置，然后直接把k+tot+2的左儿子的指针清为0，就把这段区间删掉了。可以发现，比insert还简单一点。
Reverse操作
接下来，这道题的重头戏就要开始了。splay的区间操作基本原理还类似于线段树的区间操作，即延迟修改，又称打懒标记。
对于翻转（reverse）操作，我们依旧是将操作区间变成[k+1,k+tot]，然后把k和k+tot+1分别移到对应根的右儿子的位置，然后对这个右儿子的左儿子打上翻转标记即可。
Make-Same操作
对于Make-Same操作，我们同样需要先将需要操作的区间变成[k+1,k+tot]，然后把k和k+tot+1分别移到根和右儿子的位置，然后对这个右儿子的左儿子打上修改标记即可。
Get-Sum操作
对于Get-Sum操作，我们还是将操作区间变成[k+1,k+tot],然后把k和k+tot+1分别移到根和右儿子的位置，然后直接输出这个右儿子的左儿子上的sum记录的和。
Max-Sum操作
对于这个求最大子序列的操作，即Max-Sum操作，我们不能局限于最开始学最大子序列的线性dp方法，而是要注意刚开始，基本很多书都会介绍一个分治的O(nlogn)的方法，但是由于存在O(n)的方法，导致这个方法并不受重视，但是这个方法确实很巧妙，当数列存在修改操作时，线性的算法就不再适用了。
这种带修改的最大子序列的问题，最开始是由线段树来维护，具体来说就是，对于线段树上的每个节点所代表的区间，维护3个量：lx表示从区间左端点l开始的连续的前缀最大子序列。rx表示从区间右端点r开始的连续的后缀最大子序列。mx表示这个区间中的最大子序列。
那么在合并[l,mid]和[mid+1,r]时，就类似一个dp的过程了！
懒标记的处理
最后，相信认真看了的童鞋会有疑问，这个标记怎么下传呢？首先，我们在每次将k和k+tot+1移到对应的位置时，需要一个类似查找k大值的find操作，即找出在平衡树中，实际编号为k在树中中序遍历的编号，这个才是我们真正需要处理的区间端点编号，那么就好了，我们只需在查找的过程中下传标记就好了！（其实线段树中也是这么做的），因为我们所有的操作都需要先find一下，所以我们可以保证才每次操作的结果计算出来时，对应的节点的标记都已经传好了。而我们在修改时，直接修改对应节点的记录标记和懒标记，因为我们的懒标记记录的都是已经对当前节点产生贡献，但是还没有当前节点的子树区间产生贡献！然后就是每处有修改的地方都要pushup一下就好了。
-
#include<cstdio>
-
#include<algorithm>
-
#include<cstring>
-
#include<queue>
-
#define rint register int
-
#define For(i,a,b) for (rint i=a;i<=b;++i)
-
using
namespace std;
-
const
int inf=
0x3f3f3f3f;
-
const
int N=
1e6+
17;
-
int n,m,rt,cnt;
-
int a[N],id[N],fa[N],c[N][
2];
-
int sum[N],sz[N],v[N],mx[N],lx[N],rx[N];
-
bool tag[N],rev[N];
-
//tag表示是否有统一修改的标记，rev表示是否有统一翻转的标记
-
//sum表示这个点的子树中的权值和，v表示这个点的权值
-
queue<
int> q;
-
inline int read(){
-
rint x=
0,f=
1;
char ch=
getchar();
-
while (ch<
'0' || ch>
'9'){
if (ch==
'-')f=
-1;ch=
getchar();}
-
while (
'0'<=ch && ch<=
'9')x=(x<<
1)+(x<<
3)+(ch^
48),ch=
getchar();
-
return x*f;
-
}
-
inline void pushup(rint x){
-
rint l=c[x][
0],r=c[x][
1];
-
sum[x]=sum[l]+sum[r]+v[x];
-
sz[x]=sz[l]+sz[r]+
1;
-
mx[x]=
max(mx[l],
max(mx[r],rx[l]+v[x]+lx[r]));
-
lx[x]=
max(lx[l],sum[l]+v[x]+lx[r]);
-
rx[x]=
max(rx[r],sum[r]+v[x]+rx[l]);
-
}
-
//上传记录标记
-
inline void pushdown(rint x){
-
rint l=c[x][
0],r=c[x][
1];
-
if (tag[x]){
-
rev[x]=tag[x]=
0;
//我们有了一个统一修改的标记，再翻转就没有什么意义了
-
if (l)tag[l]=
1,v[l]=v[x],sum[l]=v[x]*sz[l];
-
if (r)tag[r]=
1,v[r]=v[x],sum[r]=v[x]*sz[r];
-
if (v[x]>=
0){
-
if (l)lx[l]=rx[l]=mx[l]=sum[l];
-
if (r)lx[r]=rx[r]=mx[r]=sum[r];
-
}
else{
-
if (l)lx[l]=rx[l]=
0,mx[l]=v[x];
-
if (r)lx[r]=rx[r]=
0,mx[r]=v[x];
-
}
-
}
-
if (rev[x]){
-
rev[x]=
0;rev[l]^=
1;rev[r]^=
1;
-
swap(lx[l],rx[l]);
swap(lx[r],rx[r]);
-
//注意，在翻转操作中，前后缀的最长上升子序列都反过来了，很容易错
-
swap(c[l][
0],c[l][
1]);
swap(c[r][
0],c[r][
1]);
-
}
-
}
-
//下传标记
-
inline void rotate(rint x,rint &k){
-
rint y=fa[x],z=fa[y],l=(c[y][
1]==x),r=l^
1;
-
if (y==k)k=x;
else c[z][c[z][
1]==y]=x;
-
fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
-
c[y][l]=c[x][r];c[x][r]=y;
-
pushup(y);
pushup(x);
-
//旋转操作，一定要上传记录标记
-
}
-
inline void splay(rint x,rint &k){
-
while (x!=k){
-
int y=fa[x],z=fa[y];
-
if (y!=k){
-
if (c[z][
0]==y ^ c[y][
0]==x)
rotate(x,k);
-
else
rotate(y,k);
-
}
-
rotate(x,k);
-
}
-
}
-
//这是整个程序的核心之一，毕竟是伸展操作嘛
-
inline int find(rint x,rint rk){
-
pushdown(x);
-
//因为所有的操作都需要find，所以我们只需在这里下传标记就行了
-
rint l=c[x][
0],r=c[x][
1];
-
if (sz[l]+
1==rk)
return x;
-
if (sz[l]>=rk)
return
find(l,rk);
-
else
return
find(r,rk-sz[l]
-1);
-
}
-
//这个find是我们整个程序的核心之二
-
//因为我们的区间翻转和插入及删除的操作的存在
-
//我们维护的区间的实际编号并不是连续的
-
//而，我们需要操作的区间又对应着平衡树的中序遍历中的那段区间
-
//所以这个find很重要
-
inline void recycle(rint x){
-
rint &l=c[x][
0],&r=c[x][
1];
-
if (l)
recycle(l);
-
if (r)
recycle(r);
-
q.
push(x);
-
fa[x]=l=r=tag[x]=rev[x]=
0;
-
}
-
//这就是用时间换空间的回收冗余编号机制，很好理解
-
inline int split(rint k,rint tot){
-
rint x=
find(rt,k),y=
find(rt,k+tot+
1);
-
splay(x,rt);
splay(y,c[x][
1]);
-
return c[y][
0];
-
}
-
//这个split操作是整个程序的核心之三
-
//我们通过这个split操作，找到[k+1,k+tot]，并把k,和k+tot+1移到根和右儿子的位置
-
//然后我们返回了这个右儿子的左儿子，这就是我们需要操作的区间
-
inline void query(rint k,rint tot){
-
rint x=
split(k,tot);
-
printf(
"%d\n",sum[x]);
-
}
-
inline void modify(rint k,rint tot,rint val){
-
rint x=
split(k,tot),y=fa[x];
-
v[x]=val;tag[x]=
1;sum[x]=sz[x]*val;
-
if (val>=
0)lx[x]=rx[x]=mx[x]=sum[x];
-
else lx[x]=rx[x]=
0,mx[x]=val;
-
pushup(y);
pushup(fa[y]);
-
//每一步的修改操作，由于父子关系发生改变
-
//及记录标记发生改变，我们需要及时上传记录标记
-
}
-
inline void rever(rint k,rint tot){
-
rint x=
split(k,tot),y=fa[x];
-
if (!tag[x]){
-
rev[x]^=
1;
-
swap(c[x][
0],c[x][
1]);
-
swap(lx[x],rx[x]);
-
pushup(y);
pushup(fa[y]);
-
}
-
//同上
-
}
-
inline void erase(rint k,rint tot){
-
rint x=
split(k,tot),y=fa[x];
-
recycle(x);c[y][
0]=
0;
-
pushup(y);
pushup(fa[y]);
-
//同上
-
}
-
inline void build(rint l,rint r,rint f){
-
rint mid=(l+r)>>
1,now=id[mid],pre=id[f];
-
if (l==r){
-
mx[now]=sum[now]=a[l];
-
tag[now]=rev[now]=
0;
-
//这里这个tag和rev的清0是必要，因为这个编号可能是之前冗余了
-
lx[now]=rx[now]=
max(a[l],
0);
-
sz[now]=
1;
-
}
-
if (l<mid)
build(l,mid
-1,mid);
-
if (mid<r)
build(mid+
1,r,mid);
-
v[now]=a[mid]; fa[now]=pre;
-
pushup(now);
-
//上传记录标记
-
c[pre][mid>=f]=now;
-
//当mid>=f时，now是插入到又区间取了，所以c[pre][1]=now，当mid<f时同理
-
}
-
inline void insert(rint k,rint tot){
-
For(i,
1,tot)a[i]=
read();
-
For(i,
1,tot)
-
if (!q.
empty())id[i]=q.
front(),q.
pop();
-
else id[i]=++cnt;
//利用队列中记录的冗余节点编号
-
build(
1,tot,
0);
//将读入的tot个树建成一个平衡树
-
rint z=id[(
1+tot)>>
1];
//取中点为根
-
rint x=
find(rt,k+
1),y=
find(rt,k+
2);
-
//首先，依据中序遍历，找到我们需要操作的区间的实际编号
-
splay(x,rt);
splay(y,c[x][
1]);
-
//把k+1(注意我们已经右移了一个单位）和(k+1)+1移到根和右儿子
-
fa[z]=y;c[y][
0]=z;
-
//直接把需要插入的这个平衡树挂到右儿子的左儿子上去就好了
-
pushup(y);
pushup(x);
-
//上传记录标记
-
}
-
//对于具体在哪里上传标记和下传标记
-
//可以这么记，只要用了split就要重新上传标记
-
//只有find中需要下传标记
-
//但其实，你多传几次是没有关系的，但是少传了就不行了
-
int main(){
-
n=
read(),m=
read();
-
mx[
0]=a[
1]=a[n+
2]=-inf;
-
For(i,
1,n)a[i+
1]=
read();
-
For(i,
1,n+
2)id[i]=i;
//虚拟了两个节点1和n+2，然后把需要操作区间整体右移一个单位
-
build(
1,n+
2,
0);
//建树
-
rt=(n+
3)>>
1;cnt=n+
2;
//取最中间的为根
-
rint k,tot,val;
char ch[
10];
-
while (m--){
-
scanf(
"%s",ch);
-
if (ch[
0]!=
'M' || ch[
2]!=
'X') k=
read(),tot=
read();
-
if (ch[
0]==
'I')
insert(k,tot);
-
if (ch[
0]==
'D')
erase(k,tot);
-
if (ch[
0]==
'M'){
-
if (ch[
2]==
'X')
printf(
"%d\n",mx[rt]);
-
else val=
read(),
modify(k,tot,val);
-
}
-
if (ch[
0]==
'R')
rever(k,tot);
-
if (ch[
0]==
'G')
query(k,tot);
-
}
-
return
0;
-
}
E - 文本编辑器
平衡树的模板题。这里使用的是非旋Treap。由于这道题用平衡树维护的是文本，所以只需要考虑文字之间的相对顺序，因此之后所有对于树的split操作指的都是按照排名进行split。
不难想到用一个变量p存下来光标前面一个字符的下标（下标从11开始）。下面考虑对于题目中各个操作的处理：
1.Move,Prev,Next：对于这三个操作，修改p即可。
2.Delete：设文本为S。把树分成三个部分，一个为x树，对应[1,p]的文本；一个为y树，对应要删除的(p,p+n]的文本；还有一个为z树，对应(p+n,∣S∣]的文本。于是乎y树就是要删除的部分。我们直接将x树和z树合成新树即可。
3.Rotate：同上，把需要修改的部分提出来，打标记。然后在拆分、修改的操作的时候下传标记即可。
4.Get：相当于求文本中第p+1小的值。套板子。
5.Insert：先把书分成两个部分，一个为x树，对应[1,p]；另一个为z树，对应(p,∣S∣]。下面有两种处理方法。一种是把要插入的串暴力一个一个字符地插入到x树，然后合并x和z，时间是可以过的，但是显然效率很低；另一种是对于要插入的串建立一颗y树，再把x,y,z合并起来。因为我很懒，我用的第一种方法。
由于出题人很恶心，插入的时候有可能出现换行符也需要插入，所以需要严格地按照输入的n来插入而不是用scanf之类的。同时，如果Get需要输出换行符，就只需要输出一个。
然后你就发现这道黑题就被这样愉快地水过去解决了。
-
#include <cstdio>
-
#include <cstdlib>
-
#include <cstring>
-
-
#define random myRandom
-
-
const
int MAXSIZ =
1024 *
1024 *
2 +
5;
-
-
template<typename _T>
-
void
read
( _T &x )
-
{
-
x =
0;
char s =
getchar();
int f =
1;
-
while( s >
'9' || s <
'0' ){
if( s ==
'-' ) f =
-1; s =
getchar();}
-
while( s >=
'0' && s <=
'9' ){x = ( x <<
3 ) + ( x <<
1 ) + ( s -
'0' ), s =
getchar();}
-
x *= f;
-
}
-
-
template<typename _T>
-
void
write
( _T x )
-
{
-
if( x <
0 ){
putchar(
'-' ); x = ( ~ x ) +
1; }
-
if(
9 < x ){
write( x /
10 ); }
-
putchar( x %
10 +
'0' );
-
}
-
-
template<typename _T>
-
void
swapp
( _T &x, _T &y ) { _T t = x; x = y, y = t; }
-
-
int ch[MAXSIZ][
2], aux[MAXSIZ], siz[MAXSIZ];
-
char val[MAXSIZ], S[MAXSIZ];
-
bool rot[MAXSIZ];
-
int nsiz, mpos =
0, rt;
-
-
void srd() {
int a, *aa = &a;
srand( (
unsigned
long
long ) aa ); }
-
int random() {
return
rand() *
rand(); }
-
int newNode( const char c ) { aux[++ nsiz] =
random(), siz[nsiz] =
1, val[nsiz] = c, rot[nsiz] =
false;
return nsiz; }
-
void upt( const int u ) { siz[u] = siz[ch[u][
0]] + siz[ch[u][
1]] +
1; }
-
void swp( const int u ) {
swapp( ch[u][
0], ch[u][
1] ), rot[u] ^=
1; }
-
void normalize( const int u )
-
{
-
if( ! rot[u] )
return ;
-
swp( ch[u][
0] ),
swp( ch[u][
1] );
-
rot[u] =
false;
-
}
-
-
void splitRnk( const int u, const int k, int &x, int &y )
-
{
-
if( ! u ) { x = y =
0;
return ; }
-
normalize( u );
-
if( k <= siz[ch[u][
0]] ) y = u,
splitRnk( ch[u][
0], k, x, ch[u][
0] );
-
else x = u,
splitRnk( ch[u][
1], k - siz[ch[u][
0]] -
1, ch[u][
1], y );
-
upt( u );
-
}
-
-
int merg( const int u, const int v )
-
{
-
if( ! u || ! v )
return u + v;
-
if( aux[u] < aux[v] ) {
normalize( u ), ch[u][
1] =
merg( ch[u][
1], v ),
upt( u );
return u; }
-
else {
normalize( v ), ch[v][
0] =
merg( u, ch[v][
0] ),
upt( v );
return v; }
-
}
-
-
void insert( const char *buf )
-
{
-
int l =
strlen( buf ), y;
-
splitRnk( rt, mpos, rt, y );
-
for(
int i =
0 ; i < l ; i ++ ) rt =
merg( rt,
newNode( buf[i] ) );
-
rt =
merg( rt, y );
-
}
-
-
void del( const int length )
-
{
-
int x, y;
-
splitRnk( rt, mpos, rt, x ),
-
splitRnk( x, length, x, y );
-
rt =
merg( rt, y );
-
}
-
-
void rotate( const int length )
-
{
-
int x, y;
-
splitRnk( rt, mpos, rt, x ),
splitRnk( x, length, x, y );
-
swp( x ), rt =
merg(
merg( rt, x ), y );
-
}
-
-
char Get()
-
{
-
int u = rt, k = mpos +
1;
-
while(
true )
-
{
-
normalize( u );
-
if( k <= siz[ch[u][
0]] ) u = ch[u][
0];
-
else
if( k <= siz[ch[u][
0]] +
1 )
return val[u];
-
else k -= siz[ch[u][
0]] +
1, u = ch[u][
1];
-
}
-
}
-
-
int main()
-
{
-
srd();
-
char op[
10];
-
int N, k;
-
read( N );
-
while( N -- )
-
{
-
scanf(
"%s", op );
-
if( op[
0] ==
'M' ) {
read( mpos ); }
-
if( op[
0] ==
'I' )
-
{
-
read( k );
-
for(
int i =
0 ; i < k ; i ++ ) S[i] =
getchar();
-
insert( S );
-
for(
int i =
0 ; i < k ; i ++ ) S[i] =
'\0';
-
}
-
if( op[
0] ==
'D' )
read( k ),
-
del( k );
-
if( op[
0] ==
'R' )
read( k ),
rotate( k );
-
if( op[
0] ==
'G' )
-
{
-
char tmp;
putchar( tmp =
Get() );
-
if( tmp ^
'\n' )
putchar(
'\n' );
-
}
-
if( op[
0] ==
'P' ) mpos --;
-
if( op[
0] ==
'N' ) mpos ++;
-
}
-
return
0;
-
}
转载：https://blog.csdn.net/m0_61735576/article/details/128720370
查看评论