$$\LARGE{\color{purple}{\mathbf{Note-算法进阶课} } }$$
维护数列
0. 题目描述
请写一个程序,支持:
1. 在序列的第 $K$ 个数后插入连续的 $tot$ 个数
2. 删除序列的第 $K$ 个数(包括)之后的连续的 $tot$ 个数
3. 修改序列的第 $K$ 个数(包括)之后的连续的 $tot$ 个数为 $c$
4. 翻转序列的第 $K$ 个数(包括)之后的连续的 $tot$ 个数
5. 求和序列的第 $K$ 个数(包括)之后的连续的 $tot$ 个数
6. 求序列的第 $K$ 个数(包括)之后的连续的 $tot$ 个数的区间的最大子列和
1. 分析
(1). 维护最大连续子段和 :
标识 | 作用 | 维护方式 |
---|---|---|
ls | 最大前缀和 | max(左子树的ls,左子树的 sum + 右子树的 ls+根节点的 v) |
rs | 最大后缀和 | max(右子树的rs,右子树的 sum + 左子树的 rs + 根节点的 v) |
ms | 最大连续子段和 | max(左子树的 ls,右子树的 rs,左子树的 rs + 右子树的 rs + 根节点的值) |
sum | 区间和 | 左子树的区间和 + 右子树的区间和 + 根节点的值 |
(2). 寻找第 $K$ 个数 :
这个功能的实现只要维护一个 $size$ 信息,表示以当前节点为根节点的子树的节点个数
(3). 维护区间推平 & 翻转操作 :
因为懒标记会对我们存的值产生影响,所以需要考虑:
Q.确定节点存的信息是懒标记前的,还是懒标记后的:
A.这个题信息存的是懒标记操作之后的值,因为当前做下标记后没有及时存储操作后的信息
所以当下一次操作改变了这部分树的结构(比如 splay)的时候,就彻底乱了
所以遍历到标记后,意味着我们要对两个子树的信息进行更新
(3). 将一个序列建成 splay :
比较正确的做法是类似于线段树的建树,比较沙雕的写法也可以建成一条链。
int build(int l,int r,int p)
{
int mid = l + r >> 1;
int u = nodes[tot -- ];
tr[u].init(w[mid],p);
if(l < mid) tr[u].s[0] = build(l,mid - 1,u);
if(r > mid) tr[u].s[1] = build(mid + 1,r,u);
pushup(u);
return u;
}
(4). splay取出区间 $\[L,R]$ :
找到第 $L - 1$ 个数,用 splay 将其转到根节点,然后找到 R + 1 个数
将其转到根节点的下面,设这个节点为 $A$
于是 $\[L,R]$ 为 $A$ 的左儿子
(5). splay内存回收机制 :
使用一个栈记录能够开的空间,先将数组最大空间的节点数装进栈。
当我们要开一个节点,从栈中弹出一个节点;
当我们回收一个节点,入栈这个节点的地址。
(6). 区间赋值为 $c$ 与翻转:
给目标区间的根节点打上懒标记后,先对根节点进行相应的区间赋值与相应的翻转操作
ps : 每次改动树结构后需要考虑是不是需要 pushup 操作
code
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 500010;
constexpr int INF = 1E9;
struct Node
{
int s[2],v,p;
int sz,sum,ls,rs,rev,same,ms;
void init(int _v,int _p)
{
s[0] = s[1] = 0;
rev = same = 0;
sz = 1,v = _v,p = _p;
sum = v,ls = rs = max(v,0);
ms = v;
}
}tr[N];
int root,nodes[N],tot;
int w[N];
void pushup(int x)
{
auto &u = tr[x],&l = tr[tr[x].s[0]],&r = tr[tr[x].s[1]];
u.sz = l.sz + r.sz + 1;
u.sum = l.sum + r.sum + u.v;
u.ls = max(l.ls,l.sum + u.v + r.ls);
u.rs = max(r.rs,r.sum + u.v + l.rs);
u.ms = max(l.ms,r.ms);
u.ms = max(u.ms,l.rs + r.ls + u.v);
}
void pushdown(int x)
{
auto &u = tr[x],&l = tr[tr[x].s[0]],&r = tr[tr[x].s[1]];
if(u.same)
{
u.same = u.rev = 0;
if(u.s[0]) l.same = 1,l.sum = u.v * l.sz,l.v = u.v;
if(u.s[1]) r.same = 1,r.sum = u.v * r.sz,r.v = u.v;
if(u.v > 0)
{
if(u.s[0]) l.ls = l.rs = l.ms = l.sum;
if(u.s[1]) r.ls = r.rs = r.ms = r.sum;
}
else
{
if(u.s[0]) l.ls = l.rs = 0,l.ms = u.v;
if(u.s[1]) r.ls = r.rs = 0,r.ms = u.v;
}
}
else if(u.rev)
{
u.rev = 0;
if(u.s[0]) l.rev ^= 1;
if(u.s[1]) r.rev ^= 1;
swap(l.ls,l.rs),swap(r.rs,r.ls);
swap(l.s[0],l.s[1]),swap(r.s[0],r.s[1]);
}
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = (x == tr[y].s[1]);
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z != k)
if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root = x;
}
int kth(int k)
{
int u = root;
while(u)
{
pushdown(u);
if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].sz + 1 == k) return u;
else k -= tr[tr[u].s[0]].sz + 1,u = tr[u].s[1];
}
return -1;
}
int build(int l,int r,int p)
{
int mid = l + r >> 1;
int u = nodes[tot -- ];
tr[u].init(w[mid],p);
if(l < mid) tr[u].s[0] = build(l,mid - 1,u);
if(r > mid) tr[u].s[1] = build(mid + 1,r,u);
pushup(u);
return u;
}
void dfs(int u)
{
if(tr[u].s[0]) dfs(tr[u].s[0]);
if(tr[u].s[1]) dfs(tr[u].s[1]);
nodes[++ tot ] = u;
}
int main()
{
fastio();
int n,m;cin >> n >> m;
for(int i = 1;i < N;i ++ ) nodes[++ tot] = i;
for(int i = 1;i <= n;i ++ ) cin >> w[i];
tr[0].ms = w[0] = w[n + 1] = -INF;
root = build(0,n + 1,0);
while(m -- )
{
char str[20];
cin >> str;
if(!strcmp(str,"INSERT"))
{
int pos,cnt;cin >> pos >> cnt;
for(int i = 0;i < cnt;i ++ ) cin >> w[i];
int L = kth(pos + 1),R = kth(pos + 2);
splay(L,0),splay(R,L);
tr[R].s[0] = build(0,cnt - 1,R);
pushup(R),pushup(L);
}
else if(!strcmp(str,"DELETE"))
{
int pos,cnt;cin >> pos >> cnt;
int L = kth(pos),R = kth(pos + cnt + 1);
splay(L,0),splay(R,L);
dfs(tr[R].s[0]),tr[R].s[0] = 0;
pushup(R),pushup(L);
}
else if(!strcmp(str,"MAKE-SAME"))
{
int pos,cnt,c;cin >> pos >> cnt >> c;
int L = kth(pos),R = kth(pos + cnt + 1);
splay(L,0),splay(R,L);
auto &u = tr[tr[R].s[0]];
u.same = 1,u.sum = c * u.sz,u.v = c;
if(c > 0) u.ls = u.rs = u.ms = u.sum;
else u.ls = u.rs = 0,u.ms = c;
pushup(R),pushup(L);
}
else if(!strcmp(str,"REVERSE"))
{
int pos,cnt;cin >> pos >> cnt;
int L = kth(pos),R = kth(pos + cnt + 1);
splay(L,0),splay(R,L);
auto &u = tr[tr[R].s[0]];
u.rev = 1,swap(u.ls,u.rs),swap(u.s[0],u.s[1]);
pushup(R),pushup(L);
}
else if(!strcmp(str,"GET-SUM"))
{
int pos,cnt;cin >> pos >> cnt;
int L = kth(pos),R = kth(pos + cnt + 1);
splay(L,0),splay(R,L);
auto &u = tr[tr[R].s[0]];
cout << u.sum << endl;
}
else cout << tr[root].ms << endl;
}
return 0;
}