洛谷 P2042 [NOI2005]维护数列
题目描述
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
输入输出格式
输入格式：
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格
输出格式：
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占一行。
输入输出样例
输入样例#1： 复制
9 8 2 -6 3 5 1 -5 -3 6 3 GET-SUM 5 4 MAX-SUM INSERT 8 3 -5 7 2 DELETE 12 1 MAKE-SAME 3 3 2 REVERSE 3 6 GET-SUM 5 4 MAX-SUM
输出样例#1： 复制
-1 10 1 10
说明
你可以认为在任何时刻，数列中至少有 1 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
50%的数据中，任何时刻数列中最多含有 30 000 个数；
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。
解题思路
先建树，根据循序列的顺序，用递归的方式建立一颗平衡二叉树，使其中序遍历结果为原序列。
除了原序列1-n个数，还有加入第0个数和低n+1个数，作为1的前驱，n的后继。此时，若从1开始计数，原来的第n个数均变为n+1个数，所以以下按照1-n+2。
1.INSERT
要在第pos+1个数后面插入tot个数，就是在pos+2个数前面插入tot个数。所以把pos+1旋转到根，把pos+2旋转到pos的右孩子，然后把要插入的那些树建成一个平衡二叉树，将其根节点接到pos+1+tot的孩子上。更新pos+2，更新pos+1。
2.DELETE
将pos旋转到根，pos+1+tot旋转到pos的右孩子，然后删掉pos+1+tot的左子树。由于数据量很大，所以要把删掉的节点入队，重复利用。更新pos+1+tot，更新pos。
3.MAKE-SAME
把pos旋转到根，pos+1+tot旋转到pos的右孩子，然后给pos+1+tot的左孩子x打上标记，表示这个区间需要MAKE-SAME。改变x的各项对应的值。（此操作改变了这个区间的和，这个点的值，这个区间的最大前缀后缀，这个区间的最大字串）。更新pos+1+tot，更新pos。
4.REVERSE
把pos旋转到根，pos+1+tot旋转到pos的右孩子，然后给pos+1+tot的左孩子x打上标记，表示这个区间需要翻转。改变x的各项对应的值。（此操作交换了这个区间的左右孩子和前后缀）。更新pos+1+tot，更新pos。
5.MAKE-SUM
把pos旋转到根，pos+1+tot旋转到pos的右孩子，然后输出pos+1+tot的左孩子的和即可。
6.MAX-SUM
假设lx为最大前缀，rx为最大后缀，mx为最大子串, v为该节点的值。
那么有
lx = max(left_lx, left_sum + v + right_lx);
rx = max(right_rx, right_sum + v + left_rx);
mx = max(max(left_mx, right_mx), left_rx + v + right_lx);
根据以上状态转移方程维护。
代码如下
#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 1000005
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int v[maxn], ch[maxn][2], fa[maxn]; //值， 左右孩子， 父节点
ll lx[maxn], rx[maxn], mx[maxn]; //最大前缀，最大后缀， 最大子串
ll sum[maxn], size[maxn];
bool rev[maxn], sa[maxn]; //翻转标记，改为相同标记
int root;
int t[maxn]; //建树用数组
int cnt;
queue<int> que;
int crepoint(int x, int father) //创建节点
{
int p;
if(!que.empty()){ //重复利用
p = que.front();
que.pop();
}
else
p = ++ cnt;
sum[p] = v[p] = x;
size[p] = 1;
fa[p] = father;
lx[p] = rx[p] = max(x, 0);
mx[p] = x;
ch[p][0] = ch[p][1] = 0;
rev[p] = sa[p] = 0;
return p;
}
void push_up(int k) //更新节点
{
sum[k] = sum[ch[k][0]] + sum[ch[k][1]] + v[k];
size[k] = size[ch[k][0]] + size[ch[k][1]] + 1;
lx[k] = max(lx[ch[k][0]], sum[ch[k][0]] + lx[ch[k][1]] + v[k]);
rx[k] = max(rx[ch[k][1]], sum[ch[k][1]] + rx[ch[k][0]] + v[k]);
mx[k] = max(max(mx[ch[k][0]], mx[ch[k][1]]), rx[ch[k][0]] + v[k] + lx[ch[k][1]]);
}
void push_down(int k) //下传标记
{
if(sa[k]){
sa[k] = rev[k] = 0; //如果都变的一样，就没有必要翻转了
sa[ch[k][0]] = sa[ch[k][1]] = 1;
v[ch[k][0]] = v[ch[k][1]] = v[k];
if(ch[k][0])
sum[ch[k][0]] = size[ch[k][0]] * v[k];
if(ch[k][1])
sum[ch[k][1]] = size[ch[k][1]] * v[k];
if(v[k] >= 0){
mx[ch[k][0]] = rx[ch[k][0]] = lx[ch[k][0]] = sum[ch[k][0]];
mx[ch[k][1]] = rx[ch[k][1]] = lx[ch[k][1]] = sum[ch[k][1]];
}
else {
rx[ch[k][0]] = lx[ch[k][0]] = 0;//最大前缀后缀可以没有数，因为在dp的时候可以不要这个，就是0
mx[ch[k][0]] = v[k]; //最大字串至少有一个数
rx[ch[k][1]] = lx[ch[k][1]] = 0;
mx[ch[k][1]] = v[k];
}
}
if(rev[k]){
rev[k] = 0;
rev[ch[k][0]] ^= 1;
rev[ch[k][1]] ^= 1;
swap(ch[ch[k][0]][0], ch[ch[k][0]][1]);
swap(ch[ch[k][1]][0], ch[ch[k][1]][1]);
swap(lx[ch[k][0]], rx[ch[k][0]]); //翻转这个区间之后，这个区间内的前缀变成了后缀，后缀变成了前缀
swap(lx[ch[k][1]], rx[ch[k][1]]);
}
}
bool get(int k)
{
return ch[fa[k]][1] == k;
}
void connect(int child, int father, int u)
{
fa[child] = father;
ch[father][u] = child;
}
void rotate(int x)
{
int y = fa[x];
int z = fa[y];
int u = get(x);
int v = get(y);
connect(ch[x][u^1], y, u);
connect(x, z, v);
connect(y, x, u^1);
push_up(y);
push_up(x);
}
void splay(int now, int to)
{
if(to == root)
root = now;
to = fa[to];
while(fa[now] != to){
int up = fa[now];
if(fa[up] == to)
rotate(now);
else if(get(now) == get(up)){
rotate(up);
rotate(now);
}
else {
rotate(now);
rotate(now);
}
}
}
int build(int l, int r, int f) //建立平衡二叉树
{
if(l > r)
return 0;
int mid = (l + r) / 2;
int p = crepoint(t[mid], f);
ch[p][0] = build(l, mid - 1, p);
ch[p][1] = build(mid + 1, r, p);
push_up(p);
return p;
}
int fid(int x) //找节点
{
int now = root;
while(now){
push_down(now); //下传标记
int left = ch[now][0];
if(x <= size[left])
now = left;
else if(x == size[left] + 1){
return now;
}
else {
x -= size[left] + 1;
now = ch[now][1];
}
}
}
int split(int pos, int tot) //构建区间
{
int l = fid(pos);
int r = fid(pos + tot + 1);
splay(l, root);
splay(r, ch[l][1]);
return ch[r][0];
}
void insert(int pos, int tot)
{
int l = fid(pos + 1);
int r = fid(pos + 2);
splay(l, root);
splay(r, ch[l][1]);
for(int i = 1; i <= tot; i ++)
cin >> t[i];
ch[r][0] = build(1, tot, r); //把建好的树的根节点连到r的左子树上
push_up(r);
push_up(l);
}
void recycle(int now) //回收利用废弃节点
{
if(ch[now][0])
recycle(ch[now][0]);
if(ch[now][1])
recycle(ch[now][1]);
que.push(now);
}
void del(int pos, int tot)
{
int x = split(pos, tot);
ch[fa[x]][0] = 0; //把这个区间删除
push_up(fa[x]);
push_up(fa[fa[x]]);
recycle(x);
}
void make_same(int pos, int tot, int c)
{
int x = split(pos, tot);
sa[x] = 1; //打上标记
v[x] = c;
sum[x] = c * size[x];
if(c > 0)
lx[x] = rx[x] = mx[x] = sum[x];
else {
lx[x] = rx[x] = 0;
mx[x] = c;
}
push_up(fa[x]);
push_up(fa[fa[x]]);
}
void reverse(int pos, int tot)
{
int x = split(pos, tot);
if(!sa[x]){
rev[x] ^= 1;
swap(ch[x][0], ch[x][1]);
swap(lx[x], rx[x]);
push_up(fa[x]);
push_up(fa[fa[x]]);
}
}
ll get_sum(int pos, int tot)
{
int x = split(pos, tot);
return sum[x];
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
t[0] = -INF; //保证在选max_sum的时候不会选到
t[n + 1] = -INF;
mx[0] = -INF;
for(int i = 1; i <= n; i ++)
cin >> t[i];
root = build(0, n + 1, 0);
for(int i = 1; i <= m; i ++){
string str;
cin >> str;
if(str == "MAX-SUM"){
cout << mx[root] << "\n";
}
else {
int pos, tot;
cin >> pos >> tot;
if(str == "INSERT"){
insert(pos, tot);
}
else if(str == "DELETE"){
del(pos, tot);
}
else if(str == "MAKE-SAME"){
int c;
cin >> c;
make_same(pos, tot, c);
}
else if(str == "REVERSE"){
reverse(pos, tot);
}
else if(str == "GET-SUM"){
cout << get_sum(pos, tot) << "\n";
}
}
}
return 0;
}