维护差分信息
P4243 [JSOI2009] 等差数列
若要在序列上处理等差数列，可以考虑差分法。此时，我们不必将差分数组和数列中的元素一一对应（这会影响理解），而是将差分数组中的一个元素和原序列中对应的两个元素关联（我的理解盲区）。
这样，使用线段树时，对于（差分数组的下标）区间 \([l,r]\)，我们可以记录 \([l,r]\)，\([l,r-1]\)，\([l+1,r]\)，\([l+1,r-1]\) 的答案；合并时，通过考虑这些区间对应到原序列的哪些元素，对左右区间的重合部分统计额外贡献，不重合的情况直接相加。
对于较短的区间（\(len\le 2\)），如何处理边界条件？当 \(len=1\) 时，区间 \([l+1,r]\) 或 \([l,r-1]\) 的答案在差分数组上无意义，但却能对应到原数组上的 \(1\) 个元素；对于 \([l+1,r-1]\)，它在两个数组上都没有意义，因此直接赋值为 \(0\) 或 \(\pm\infty\)。
\(1\) 条差分信息 -> 约束两个位置
\(n\) 条差分信息 -> 约束 \(n+1\) 个位置
|
V
\(0\) 条差分信息 -> 代表一个位置
代码
#include<iostream>
using namespace std;
const int N = 1E5 + 10;
const int INF = 1E7 + 10;
struct Node {
int mans, lans, rans, ans, tag;
int ld, rd, len;
Node(int _ma = 0, int _la = 0, int _ra = 0, int _a = 0, int _ld = 0, int _rd = 0, int _tg = 0, int _len = 0) {
mans = _ma;
lans = _la;
rans = _ra;
ans = _a;
ld = _ld;
rd = _rd;
tag = _tg;
len = _len;
}
};
inline Node operator+(const Node &a, const Node &b) {
Node res;
res.mans = min(a.rans + b.lans - (a.rd == b.ld), min(a.mans + b.lans, a.rans + b.mans));
res.lans = min(a.ans + b.lans - (a.rd == b.ld), min(a.lans + b.lans, a.ans + b.mans));
res.rans = min(a.rans + b.ans - (a.rd == b.ld), min(a.mans + b.ans, a.rans + b.rans));
res.ans = min(a.ans + b.ans - (a.rd == b.ld), min(a.lans + b.ans, a.ans + b.rans));
res.ld = a.ld;
res.rd = b.rd;
return res;
}
int n, q;
int a[N], d[N];
namespace Seg_T {
inline int lc(int x) { return x << 1; }
inline int rc(int x) { return x << 1 | 1; }
Node tr[4 * N];
inline void push_up(int p) {
tr[p] = tr[lc(p)] + tr[rc(p)];
}
inline void move_tag(int p, int tg) {
tr[p].ld += tg;
tr[p].rd += tg;
tr[p].tag += tg;
}
inline void push_down(int p) {
if(!tr[p].tag) return;
move_tag(lc(p), tr[p].tag);
move_tag(rc(p), tr[p].tag);
tr[p].tag = 0;
}
void build(int p, int l, int r) {
if(l == r) {
tr[p] = {0, 1, 1, 1, d[l], d[l], 0};
return;
}
int mid = (l + r) >> 1;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
push_up(p);
}
void modify(int p, int l, int r, int q, int v) {
if(l == r) {
tr[p].ld += v;
tr[p].rd += v;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(mid >= q) modify(lc(p), l, mid, q, v);
else modify(rc(p), mid + 1, r, q, v);
push_up(p);
}
void modify(int p, int l, int r, int ql, int qr, int v) {
if(ql <= l && r <= qr) {
move_tag(p, v);
return;
}
push_down(p);
int mid = (l + r) >> 1;
if(mid >= ql) modify(lc(p), l, mid, ql, qr, v);
if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
push_up(p);
}
Node query(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return tr[p];
}
push_down(p);
int mid = (l + r) >> 1;
if(mid >= qr) return query(lc(p), l, mid, ql, qr);
if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
return query(lc(p), l, mid, ql, qr) + query(rc(p), mid + 1, r, ql, qr);
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = a[i] - a[i - 1];
}
Seg_T::build(1, 1, n + 1);
cin >> q;
while(q--) {
char op;
cin >> op;
if(op == 'A') {
int l, r, a, b;
cin >> l >> r >> a >> b;
if(l == r) {
Seg_T::modify(1, 1, n + 1, l, a);
Seg_T::modify(1, 1, n + 1, r + 1, -a);
continue;
}
Seg_T::modify(1, 1, n + 1, l, a);
Seg_T::modify(1, 1, n + 1, l + 1, r, b);
Seg_T::modify(1, 1, n + 1, r + 1, -a - (r - l) * b);
} else {
int l, r;
cin >> l >> r;
if(l == r) {
cout << 1 << '\n';
continue;
}
cout << Seg_T::query(1, 1, n + 1, l + 1, r).ans << '\n';
}
}
return 0;
}
主席树
主席树是可持久化权值线段树的简称，可以在 \(O(\log V)\) 的时间和空间复杂度内实现一次插入，同时可以保存所有历史版本。
模板代码
#include<iostream>
using namespace std;
const int N = 1E6 + 10;
const int LOGN = 25;
int n, q;
int a[N], rt[N];
namespace Seg_T {
int nn;
int lc[N * LOGN], rc[N * LOGN], sum[N * LOGN];
int addNode(int p) {
int nw = ++nn;
lc[nw] = lc[p];
rc[nw] = rc[p];
return nw;
}
inline void push_up(int p) {
sum[p] = sum[lc[p]] + sum[rc[p]];
}
void build(int &p, int l, int r) {
if(p == 0) p = ++nn;
if(l == r) {
sum[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lc[p], l, mid);
build(rc[p], mid + 1, r);
push_up(p);
}
int modify(int p1, int l, int r, int q, int v) {
int p = addNode(p1);
if(l == r) {
sum[p] = v;
return p;
}
int mid = (l + r) >> 1;
if(mid >= q) lc[p] = modify(lc[p1], l, mid, q, v);
else rc[p] = modify(rc[p1], mid + 1, r, q, v);
push_up(p);
return p;
}
int query(int p, int l, int r, int q) {
if(l == r) {
return sum[p];
}
int mid = (l + r) >> 1;
if(mid >= q) return query(lc[p], l, mid, q);
else return query(rc[p], mid + 1, r, q);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
Seg_T::build(rt[0], 1, n);
for(int i = 1; i <= q; i++) {
int ver, op, pos, val;
cin >> ver >> op;
if(op == 1) {
cin >> pos >> val;
rt[i] = Seg_T::modify(rt[ver], 1, n, pos, val);
} else {
cin >> pos;
cout << Seg_T::query(rt[ver], 1, n, pos) << '\n';
rt[i] = rt[ver];
}
}
return 0;
}
使用主席树我们可以对原数组的每一个前缀都“建”一棵权值线段树，通过对两棵不同下标对应的树作差，我们可以对任意下标区间 \([l,r]\) 使用线段树二分，解决静态区间第 \(k\) 小的问题。
模板代码
#include<iostream>
#define int long long
using namespace std;
const int N = 2E5 + 10;
const int A = 1E9;
const int LOGA = 20;
int n, m;
int rt[N];
namespace Seg_T {
int nn;
int lc[N * LOGA], rc[N * LOGA], sum[N * LOGA];
int addNode(int p1) {
int p = ++nn;
lc[p] = lc[p1];
rc[p] = rc[p1];
sum[p] = sum[p1];
return p;
}
void push_up(int p) {
sum[p] = sum[lc[p]] + sum[rc[p]];
}
int insert(int p1, int l, int r, int q, int v) {
int p = addNode(p1);
if(l == r) {
sum[p] += v;
return p;
}
int mid = (l + r) >> 1;
if(mid >= q) lc[p] = insert(lc[p1], l, mid, q, v);
else rc[p] = insert(rc[p1], mid + 1, r, q, v);
push_up(p);
return p;
}
int queryKth(int pl, int pr, int l, int r, int k) {
if(l == r) {
return l;
}
int mid = (l + r) >> 1;
if(k <= sum[lc[pr]] - sum[lc[pl]]) return queryKth(lc[pl], lc[pr], l, mid, k);
else return queryKth(rc[pl], rc[pr], mid + 1, r, k - (sum[lc[pr]] - sum[lc[pl]]));
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
rt[i] = Seg_T::insert(rt[i - 1], 0, A, x, 1);
}
for(int i = 1; i <= m; i++) {
int l, r, k;
cin >> l >> r >> k;
cout << Seg_T::queryKth(rt[l - 1], rt[r], 0, A, k) << '\n';
}
return 0;
}
时间复杂度 \(O(n\log V)\) - \(O(m\log V)\)。