当前位置: 首页 > news >正文

P2042 [NOI2005] 维护数列 题解

P2042 [NOI2005] 维护数列 题解

平衡树

因为操作里面有翻转,严格强于文艺平衡树,所以考虑平衡树维护数列。

  1. 直接暴力插入即可
  2. 分裂出删除的子段,然后合并其两端的平衡树
  3. 分裂出修改的子段,然后打推平的懒标记,
  4. 分裂出翻转的子段,交换根的左右子树,然后打翻转的懒标记
  5. 维护子树和
  6. 维护子树最大子段和,本题子段不可为空。

因为要维护最大子段和,在翻转的时候需要交换左边开始最大和与右边开始最大和,这里我们维护左右最大和的时候可以为空,因为平衡树上传信息的时候包含当前节点(非 leafy tree),所以自然不会得到空子段。

注意到本题空间限制只有 128Mb,需要回收删除的节点减少空间消耗。

时间复杂度:\(O(N\log N)\)

// Problem: P2042 [NOI2005] 维护数列
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2025 Moyou All rights reserved.
// Date: 2025-09-02 22:52:54#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <random>
#include <ctime>
// #define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10, M = 4e6 + 10, INF = 1e9;int n, m, tag[N], rvs[N], sum[N], dat[N], lm[N], rm[N], ls[N], rs[N], siz[N], val[N], rnd[N], rt, idx, trash[M], tott;
mt19937 rando(time(0));
int New(int u) {int p = trash[tott];if(!tott) p = ++ idx;else tott --;// int p = ++ idx;tag[p] = -INF, ls[p] = rs[p] = rvs[p] = 0;val[p] = u, sum[p] = u, dat[p] = u, lm[p] = rm[p] = max(0, u);rnd[p] = rando(), siz[p] = 1;return p;
} 
void up(int u) {siz[u] = siz[ls[u]] + siz[rs[u]] + 1;sum[u] = sum[ls[u]] + sum[rs[u]] + val[u];dat[u] = max({dat[ls[u]], dat[rs[u]], rm[ls[u]] + lm[rs[u]] + val[u]});lm[u] = max(lm[ls[u]], sum[ls[u]] + val[u] + lm[rs[u]]);rm[u] = max(rm[rs[u]], sum[rs[u]] + val[u] + rm[ls[u]]);
}
void align(int u, int v) {if(!u) return ;sum[u] = siz[u] * v, dat[u] = max(v, sum[u]), lm[u] = rm[u] = max(0, sum[u]), val[u] = v, tag[u] = v;
}
void Reverse(int u) {if(!u) return ;swap(ls[u], rs[u]), swap(lm[u], rm[u]), rvs[u] ^= 1;
}
void down(int u) {if(rvs[u]) Reverse(ls[u]), Reverse(rs[u]), rvs[u] = 0;if(tag[u] != -INF) align(ls[u], tag[u]), align(rs[u], tag[u]), tag[u] = -INF;
}
int merge(int a, int b) {if(!a || !b) return a + b;down(a), down(b);if(rnd[a] < rnd[b]) return rs[a] = merge(rs[a], b), up(a), a;return ls[b] = merge(a, ls[b]), up(b), b;
}
void split(int p, int v, int &a, int &b) {if(!p) return a = b = 0, void();down(p);if(siz[ls[p]] + 1 <= v) a = p, split(rs[p], v - siz[ls[p]] - 1, rs[p], b);else b = p, split(ls[p], v, a, ls[p]);up(p);
}
void reuse(int u) {if(!u) return ;trash[++ tott] = u;reuse(ls[u]), reuse(rs[u]);
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1, x; i <= n; i ++) cin >> x, rt = merge(rt, New(x));dat[0] = -INF;for(int i = 1, pos, tot, a, b, c, v; i <= m; i ++) {string s; cin >> s;if(s[0] == 'I') {cin >> pos >> tot;split(rt, pos, a, b);for(int i = 1, x; i <= tot; i ++) cin >> x, a = merge(a, New(x));rt = merge(a, b);}else if(s[0] == 'D') {cin >> pos >> tot;split(rt, pos - 1, a, b);split(b, tot, b, c);reuse(b);rt = merge(a, c);}else if(s[0] == 'M' && s.back() == 'E') {cin >> pos >> tot >> v;split(rt, pos - 1, a, b);split(b, tot, b, c);align(b, v);rt = merge(merge(a, b), c);}else if(s[0] == 'R') {cin >> pos >> tot;split(rt, pos - 1, a, b);split(b, tot, b, c);Reverse(b);rt = merge(merge(a, b), c);}else if(s[0] == 'G') {cin >> pos >> tot;split(rt, pos - 1, a, b);split(b, tot, b, c);cout << sum[b] << '\n';rt = merge(merge(a, b), c);}else {cout << dat[rt] << '\n';}}return 0;
}

DeepSeek 修改后我的代码:

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <random>
#include <ctime>
using namespace std;typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10, M = 4e6 + 10, INF = 1e9;// 平衡树节点结构
struct Node {int left, right;    // 左右子节点int value;          // 节点值int size;           // 子树大小int priority;       // 随机优先级(用于Treap)int sum;            // 子树区间和int max_sum;        // 子树最大子段和int prefix_max;     // 最大前缀和int suffix_max;     // 最大后缀和int lazy_assign;    // 区间赋值懒标记bool lazy_reverse;  // 区间反转懒标记
};Node tree[M];
int root, node_count;
int recycled_nodes[M], recycle_count;
mt19937 rng(time(0));// 创建一个新节点
int create_node(int value) {int id;if (recycle_count > 0) {id = recycled_nodes[recycle_count--];} else {id = ++node_count;}tree[id].left = tree[id].right = 0;tree[id].value = value;tree[id].size = 1;tree[id].priority = rng();tree[id].sum = value;tree[id].max_sum = value;tree[id].prefix_max = max(0, value);tree[id].suffix_max = max(0, value);tree[id].lazy_assign = -INF;tree[id].lazy_reverse = false;return id;
}// 更新节点信息
void update(int id) {if (id == 0) return;Node &node = tree[id];Node &left = tree[node.left];Node &right = tree[node.right];node.size = left.size + right.size + 1;node.sum = left.sum + right.sum + node.value;// 计算最大子段和node.max_sum = max({left.max_sum, right.max_sum, left.suffix_max + node.value + right.prefix_max});// 计算最大前缀和node.prefix_max = max(left.prefix_max, left.sum + node.value + right.prefix_max);// 计算最大后缀和node.suffix_max = max(right.suffix_max, right.sum + node.value + left.suffix_max);
}// 应用区间赋值标记
void apply_assign(int id, int value) {if (id == 0) return;Node &node = tree[id];node.value = value;node.sum = value * node.size;node.max_sum = max(value, node.sum);node.prefix_max = node.suffix_max = max(0, node.sum);node.lazy_assign = value;
}// 应用区间反转标记
void apply_reverse(int id) {if (id == 0) return;Node &node = tree[id];swap(node.left, node.right);swap(node.prefix_max, node.suffix_max);node.lazy_reverse = !node.lazy_reverse;
}// 下传标记
void push_down(int id) {if (id == 0) return;Node &node = tree[id];if (node.lazy_reverse) {apply_reverse(node.left);apply_reverse(node.right);node.lazy_reverse = false;}if (node.lazy_assign != -INF) {apply_assign(node.left, node.lazy_assign);apply_assign(node.right, node.lazy_assign);node.lazy_assign = -INF;}
}// 合并两棵树
int merge(int left, int right) {if (left == 0 || right == 0) return left + right;push_down(left);push_down(right);if (tree[left].priority < tree[right].priority) {tree[left].right = merge(tree[left].right, right);update(left);return left;} else {tree[right].left = merge(left, tree[right].left);update(right);return right;}
}// 分裂树
void split(int id, int size, int &left, int &right) {if (id == 0) {left = right = 0;return;}push_down(id);int left_size = tree[tree[id].left].size;if (left_size + 1 <= size) {left = id;split(tree[id].right, size - left_size - 1, tree[id].right, right);} else {right = id;split(tree[id].left, size, left, tree[id].left);}update(id);
}// 回收节点
void recycle_tree(int id) {if (id == 0) return;recycled_nodes[++recycle_count] = id;recycle_tree(tree[id].left);recycle_tree(tree[id].right);
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;tree[0].max_sum = -1e9;// 初始化树root = 0;for (int i = 0; i < n; i++) {int value;cin >> value;root = merge(root, create_node(value));}// 处理操作for (int i = 0; i < m; i++) {string op;cin >> op;if (op == "INSERT") {int pos, count;cin >> pos >> count;int left, right;split(root, pos, left, right);for (int j = 0; j < count; j++) {int value;cin >> value;left = merge(left, create_node(value));}root = merge(left, right);} else if (op == "DELETE") {int pos, count;cin >> pos >> count;int left, mid, right;split(root, pos - 1, left, mid);split(mid, count, mid, right);recycle_tree(mid);root = merge(left, right);} else if (op == "MAKE-SAME") {int pos, count, value;cin >> pos >> count >> value;int left, mid, right;split(root, pos - 1, left, mid);split(mid, count, mid, right);apply_assign(mid, value);root = merge(merge(left, mid), right);} else if (op == "REVERSE") {int pos, count;cin >> pos >> count;int left, mid, right;split(root, pos - 1, left, mid);split(mid, count, mid, right);apply_reverse(mid);root = merge(merge(left, mid), right);} else if (op == "GET-SUM") {int pos, count;cin >> pos >> count;int left, mid, right;split(root, pos - 1, left, mid);split(mid, count, mid, right);cout << tree[mid].sum << '\n';root = merge(merge(left, mid), right);} else if (op == "MAX-SUM") {cout << tree[root].max_sum << '\n';}}return 0;
}

块状链表

考虑分块,结合链表和数组的优点,维护一个链表,链表里面每一项都是一个数组,维护的时候钦定数组大小不超过 \(2B\),否则分裂这个数组,如果相邻两个数组大小加起来不超过 \(B\),那么把他们合并起来,这样每个数组大小都差不多在 \(B\) 左右,类似一个动态的分块,显然块状链表有 \(O(\dfrac nB)\) 项。

块状链表的一个重要函数是 split(pos),表示把块状链表里第 \(pos\) 个数字所在数组分裂,得到的新数组编号。

  1. 插入,split(pos),然后在新数组前插入,时间复杂度 \(O(B + \dfrac nB)\)

  2. 删除,L = split(pos - 1), R = split(pos + tot - 1),然后用链表的手段删除 \([L, R)\) 内的数组,也就是让 \(prev_L\)next 指针指向 \(R\),当然如果 \(L\) 是头指针,直接让头指针变成 \(R\)

  3. 修改,还是同上,先把区间分裂出来,然后区间里面每个数组都打推平的懒标记。

  4. 翻转,先把区间分裂出来,然后注意到翻转这个区间等价于先翻转链表上数组的顺序,再翻转每个数组内元素,所以先翻转这个区间里面的数组顺序,然后给每个数组打翻转的懒标记。

  5. 求和,维护数组内和。

  6. 最大子段和,维护同平衡树做法。

Tips:

  1. 给定的数组不要忘记初始化
  2. 注意插入的时候是在数组前面插入还是后面插入
  3. tot可能为0,需要特判
  4. 删除区间的时候如果把头指针删掉了,要确定新的头指针
  5. 如果不合并相邻小数组复杂度是错的
// Problem: P2042 [NOI2005] ά»¤ÊýÁÐ
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2025 Moyou All rights reserved.
// Date: 2025-09-02 22:52:54#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <random>
#include <ctime>
// #define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10, M = 4e6 + 10, B = 300, INF = 1e9;int n, m, rvs[N], tag[N], ne[N], hd, lm[N], rm[N], sum[N], dat[N], idx;
vector<int> a[N];
void recalc(int u) {if(tag[u] != -INF) {for(auto &x : a[u]) x = tag[u];tag[u] = -INF, rvs[u] = 0;}if(rvs[u]) reverse(a[u].begin(), a[u].end()), rvs[u] = 0;lm[u] = rm[u] = sum[u] = dat[u] = -INF;if(a[u].size()) {int s = 0;for(int i = 0; i < a[u].size(); i ++)s += a[u][i], lm[u] = max(lm[u], s);// cout << "RE " << u << ' ' << a[u].size() << '\n';s = 0;for(int i = a[u].size() - 1; ~i; i --)s += a[u][i], rm[u] = max(rm[u], s);sum[u] = s;int dp = -INF;for(auto o : a[u]) {dp = max(dp + o, o);dat[u] = max(dat[u], dp);}}
}
int New(vector<int> v) {int p = ++ idx; a[p] = v, rvs[p] = 0, tag[p] = -INF, ne[p] = 0;recalc(p);return p;
}
void check(int x) {recalc(x);while(a[x].size() > B * 2) {vector<int> t;while(t.size() < B)t.push_back(a[x].back()), a[x].pop_back();reverse(t.begin(), t.end());int p = New(t);ne[p] = ne[x], ne[x] = p;}recalc(x);
}
PII split(int pos) {if(!pos) {int p = New({});ne[p] = hd, hd = p;return {0, p};}int i;for(i = hd; i; i = ne[i]) {if(pos <= a[i].size()) {check(i);}if(pos < a[i].size()) {vector<int> t;while(a[i].size() > pos) t.push_back(a[i].back()), a[i].pop_back();reverse(t.begin(), t.end());int p = New(t);ne[p] = ne[i], ne[i] = p;recalc(i);return {i, p};}else if(pos == a[i].size()) {int p = New({});ne[p] = ne[i], ne[i] = p;recalc(i);return {i, p};}pos -= a[i].size();}cout << "INF  \n";return {-1, -1};
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m, idx = 0;vector<int> t;for(int i = 1, x; i <= n; i ++) cin >> x, t.push_back(x);hd = New(t);check(hd);dat[0] = -INF;for(int i = 1, pos, tot, b, c, v; i <= m; i ++) {string s; cin >> s;if(s[0] == 'I') {cin >> pos >> tot;int L = split(pos).y;vector<int> t;for(int i = 1, x; i <= tot; i ++) cin >> x, t.push_back(x);for(int o : a[L]) t.push_back(o);a[L] = t;recalc(L);}else if(s[0] == 'D') {cin >> pos >> tot;if(!tot) continue;int L = split(pos - 1).x, R = split(pos + tot - 1).y;for(int i = ne[L]; i != R && i; i = ne[i]) {a[i] = vector<int>();}if(L) ne[L] = R;else hd = R;}else if(s[0] == 'M' && s.back() == 'E') {cin >> pos >> tot >> v;if(!tot) continue;int L = split(pos - 1).y, R = split(pos + tot - 1).x;for(int i = L; ; i = ne[i]) {tag[i] = v, rvs[i] = 0, sum[i] = a[i].size() * v;lm[i] = rm[i] = dat[i] = max(v, sum[i]);if(i == R) break;}}else if(s[0] == 'R') {cin >> pos >> tot;if(!tot) continue;auto tmp = split(pos - 1);int pl = tmp.x, L = tmp.y;tmp = split(pos + tot - 1);int R = tmp.x, nr = tmp.y;vector<int> t;for(int i = L; ; i = ne[i]) {rvs[i] ^= 1;t.push_back(i);swap(lm[i], rm[i]);if(i == R) break;}reverse(t.begin(), t.end());t.push_back(nr);if(pl) ne[pl] = R;else hd = R;for(int i = 0; i < (int)t.size() - 1; i ++)ne[t[i]] = t[i + 1];}else if(s[0] == 'G') {cin >> pos >> tot;if(!tot) {cout << 0 << '\n';continue;}int s = 0, L = split(pos - 1).y, R = split(pos + tot - 1).x;for(int i = L; ; i = ne[i]) {if(a[i].empty()) continue;s += sum[i];if(i == R) break;}cout << s << '\n';}else {int lm_ = -INF, rm_ = -INF, dat_ = -INF, sum_ = 0;for(int i = hd; i; i = ne[i]) {if(a[i].empty()) continue;dat_ = max({dat_, dat[i], rm_ + lm[i]});lm_ = max(lm_, sum_ + lm[i]);rm_ = max(rm[i], rm_ + sum[i]);sum_ += sum[i];}cout << dat_ << '\n';}while(a[hd].empty()) hd = ne[hd];for(int i = hd; i; i = ne[i]) {while(ne[i] && a[ne[i]].size() + a[i].size() <= B) {recalc(i), recalc(ne[i]);for(auto o : a[ne[i]]) a[i].push_back(o);a[ne[i]] = vector<int>();recalc(i);ne[i] = ne[ne[i]];}}}return 0;
}
http://www.hskmm.com/?act=detail&tid=16889

相关文章:

  • 达梦数据库查询字段类型为Date 修改为DateTime
  • C++ new 操作符在操作系统层执行了什么操作?
  • [ABC422F-G] 题解
  • 别再靠 “关设备” 减碳!EMS 的 “预测性控能”,让企业满产也能达标双碳
  • LAMP 架构说明及部署实践 - 教程
  • MyEMS 深度解析:核心功能模块、数据流转逻辑与工业能源优化落地路径
  • kettle插件-国产数据库金仓插件,助力国产数据库腾飞
  • 制造业碳足迹追踪:开源能源管理系统如何助力企业实现“碳数据可视化”?
  • iframe安全盲区:支付信息窃取攻击的新温床 - 教程
  • 综合网表中有assign怎么办
  • 极限与导数
  • 呼叫中心开源社区专栏第一篇 - 详解
  • 原核表达可溶性蛋白难题破解
  • 深入解析:Adobe Fresco下载教程Adobe Fresco 2025保姆级安装步骤(附安装包)
  • Torch中的tensor size
  • Codeforces 1053 (Div.2)
  • 抗体药物偶联物(ADCs)生物分析:拆解 “靶向导弹” 体内轨迹的核心技术
  • 详细介绍:微服务的适用边界:从金融科技到量子计算的架构哲学
  • 使用IOT-Tree整合复杂计算模型(含AI模型),并对接现场设备优化控制(节能提效)技能方案
  • 为什么应该测试无JavaScript的页面体验
  • 前台部分数据不显示
  • 指针定义以及二维数组内存地址(java/c++/python)
  • 解码数据结构线性表之顺序表
  • 中电金信:源启数据集成平台全新升级,实现便捷与性能双飞跃
  • Jupyter NoteBook / Jupyter Lab的安装与使用
  • 完整教程:科技的温情——挽救鼠鼠/兔兔的生命
  • 易基因:Nat Rev Drug Discov/IF101.8:何川团队顶刊综述RNA修饰系统作为疾病治疗靶点的研究进展
  • 国产适配 + AI 一键生成!亿图图示 14.5 全平台绘图指南:260 种图表 + Visio 兼容,开发者 / 办公党速藏
  • 关闭Cadence Allegro Design Entry CIS(OrCAD Capture)的Start Page
  • Mini L-CTF 2025 WP