经典数据结构问题
title: 经典数据结构问题
categories:
- ICPC
tags:
- null
abbrlink: cecfa4d9
date: 2023-03-31 00:00:00
经典数据结构问题
静态区间颜色数
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int m;
cin >> m;
int mx = *max_element(alls(a));
vector<vector<pii>> q(n + 1);
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
q[r].push_back({l, i});
}
deb("?");
Fwk<int> fwk(mx + 10);
vector<int> last(mx + 1);
auto add = [&](int l, int r, int x) {
fwk.add(l, x);
fwk.add(r + 1, -x);
};
vector<int> ans(m + 1);
deb("?");
for (int r = 1; r <= n; r++) {
add(last[a[r]] + 1, r, 1);
last[a[r]] = r;
for (auto [l, id] : q[r]) {
ans[id] = fwk.sum(l);
}
}
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}
静态区间不同数之和
void solve() {
int n, m;
cin >> n;
cin >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// int m;
// cin >> m;
int mx = *max_element(alls(a));
vector<vector<pii>> q(n + 1);
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
q[r].push_back({l, i});
}
deb("?");
Fwk<int> fwk(mx + 10);
vector<int> last(mx + 1);
auto add = [&](int l, int r, int x) {
fwk.add(l, x);
fwk.add(r + 1, -x);
};
vector<int> ans(m + 1);
deb("?");
for (int r = 1; r <= n; r++) {
add(last[a[r]] + 1, r, a[r]);
last[a[r]] = r;
for (auto [l, id] : q[r]) {
ans[id] = fwk.sum(l);
}
}
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}
静态二维数点:多次询问一个矩形内有多少个点
void solve() {
vector<int> vy;
int n, m;
cin >> n >> m;
vector<a5> event;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
vy.push_back(y);
event.push_back({x, 0, 0, y, 0});
}
Fwk<int> fwk(n + 1);
for (int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
event.push_back({x1 - 1, 1, 1, y1 - 1, i});
event.push_back({x2, 1, 1, y2, i});
event.push_back({x1 - 1, 1, -1, y2, i});
event.push_back({x2, 1, -1, y1 - 1, i});
}
sort(alls(vy));
vy.erase(unique(alls(vy)), vy.end());
sort(alls(event));
vector<int> ans(m + 1);
for (auto [x, ty, sgn, y, id] : event) {
if (ty == 0) {
int val = lower_bound(alls(vy), y) - vy.begin() + 1;
assert(val <= n);
fwk.add(val, 1);
} else {
int val = upper_bound(alls(vy), y) - vy.begin() + 1 - 1;
assert(val <= n);
ans[id] += sgn * fwk.sum(val);
}
}
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}
矩形面积并：扫描线维护最小值出现次数
template <class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) { init(vector<Info>(n_ + 1, v_)); }
LazySegmentTree(vector<Info> t_) { init(t_); }
void init(vector<Info> a) //[1,n]
{
n = a.size() - 1;
info.assign((n << 2) + 1, Info());
tag.assign((n << 2) + 1, Tag());
function<void(int, int, int)> build = [&](int x, int l, int r) -> void {
if (l == r) {
info[x] = a[l];
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
pushup(x);
};
build(1, 1, n);
}
void pushup(int x) { info[x] = info[x << 1] + info[x << 1 | 1]; }
void apply(int p, const Tag& v) {
info[p].apply(v); // 标记更新自己
tag[p].apply(v); // 下传标记
}
void pushdown(int x) {
apply(x << 1, tag[x]);
apply(x << 1 | 1, tag[x]);
tag[x] = Tag();
}
void update(int x, int l, int r, int p, const Info& v) {
if (l == r) {
info[x] = v;
return;
}
int mid = (l + r) >> 1;
pushdown(x);
if (p <= mid)
update(x << 1, l, mid, p, v);
else
update(x << 1 | 1, mid + 1, r, p, v);
pushup(x);
}
void update(int p, const Info& v) { update(1, 1, n, p, v); }
Info query(int x, int l, int r, int ql, int qr) {
if (l > qr || r < ql)
return Info();
if (ql <= l && r <= qr)
return info[x];
int mid = (l + r) >> 1;
pushdown(x);
return query(x << 1, l, mid, ql, qr) +
query(x << 1 | 1, mid + 1, r, ql, qr);
}
Info query(int ql, int qr) { return query(1, 1, n, ql, qr); }
void rangeupdate(int x, int l, int r, int ql, int qr, const Tag& v) {
if (l > qr || r < ql)
return;
if (ql <= l && r <= qr) {
apply(x, v);
return;
}
int mid = (l + r) >> 1;
pushdown(x);
rangeupdate(x << 1, l, mid, ql, qr, v);
rangeupdate(x << 1 | 1, mid + 1, r, ql, qr, v);
pushup(x);
}
void rangeupdate(int ql, int qr, const Tag& v) {
rangeupdate(1, 1, n, ql, qr, v);
}
template <class F>
int findFirst(int x, int l, int r, int ql, int qr, F pred) {
if (l > qr || r < ql || !pred(info[x]))
return -1;
if (l == r)
return l;
int mid = (l + r) >> 1;
pushdown(x);
int res = findFirst(x << 1, l, mid, ql, qr, pred);
if (res == -1)
res = findFirst(x << 1 | 1, mid + 1, r, ql, qr, pred);
return res;
}
template <class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 1, n, l, r, pred);
}
template <class F>
int findLast(int x, int l, int r, int ql, int qr, F pred) {
if (l > qr || r < ql || !pred(info[x]))
return -1;
if (l == r)
return l;
int mid = (l + r) >> 1;
pushdown(x);
int res = findLast(x << 1 | 1, mid + 1, r, ql, qr, pred);
if (res == -1)
res = findLast(x << 1, l, mid, ql, qr, pred);
return res;
}
template <class F>
int findLast(int l, int r, F pred) {
return findLast(1, 1, n, l, r, pred);
}
};
struct Tag {
ll add = 0;
void apply(const Tag& v) { add += v.add; } // 标记怎么合并
};
struct Info {
ll minv = 0, mincnt = 1;
void apply(const Tag& v) { minv += v.add; } // 标记怎么更新节点信息
};
Info operator+(const Info& a, const Info& b) { // 维护的信息怎么合并
if (a.minv == b.minv)
return {a.minv, a.mincnt + b.mincnt};
else if (a.minv < b.minv)
return a;
else
return b;
}
#define a4 array<int, 4>
void solve() {
int n;
cin >> n;
vector<a4> event;
vector<int> vy;
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
event.push_back({x1, 1, y1, y2});
event.push_back({x2, -1, y1, y2});
vy.push_back(y1);
vy.push_back(y2);
}
sort(alls(vy));
vy.erase(unique(alls(vy)), vy.end());
vector<Info> tmp(1);
int nodecnt = 0;
for (int i = 1; i < (int)vy.size(); i++) {
tmp.push_back({0, vy[i] - vy[i - 1]});
//cerr << "tmp" << i << " " << vy[i] - vy[i - 1] << endl;
nodecnt++;
}
LazySegmentTree<Info, Tag> seg(tmp);
ll ans = 0;
sort(alls(event));
int prex = 0;
ll len = seg.query(1, nodecnt).mincnt;
for (auto [x, op, y1, y2] : event) {
int idy1 = lower_bound(alls(vy), y1) - vy.begin() + 1;
int idy2 = lower_bound(alls(vy), y2) - vy.begin();
deb(x, op, y1, y2);
deb(idy1, idy2);
ll d = len;
deb(len);
auto [val, cnt] = seg.query(1, nodecnt);
if (val == 0)
d -= cnt;
deb(prex, x, d);
ans += (ll)(x - prex) * d;
prex = x;
seg.rangeupdate(idy1, idy2, {op});
}
cout << ans << endl;
}
静态区间mex:注意线段树的单点修改是赋值操作
struct Tag {
ll add = 0;
void apply(const Tag& v) { add += v.add; } // 标记怎么合并
};
struct Info {
ll sum = 0, len = 1;
void apply(const Tag& v) { sum += len * v.add; } // 标记怎么更新节点信息
};
Info operator+(const Info& a, const Info& b) { // 维护的信息怎么合并
Info c = Info();
c.sum = min(a.sum, b.sum);
c.len = a.len + b.len;
return c;
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<pii>> q(m + 1);
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
q[r].push_back({l, i});
}
vector<int> ans(m + 1);
LazySegmentTree<Info, Tag> seg(n + 10);
////map<int, int> mp;
for (int r = 1; r <= n; r++) {
a[r] = min(a[r], n + 3);
seg.update(a[r] + 1, {r, 1});
// mp[a[r] + 1] = r;
for (auto [l, id] : q[r]) {
deb(id, l, r);
ans[id] = seg.findFirst(1, n + 2, [&](Info v) {
if (v.sum < l)
return true;
return false;
});
}
}
for (int i = 1; i <= m; i++) cout << ans[i] - 1 << endl;
}
找到每个数都出现k次的区间数量
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define R(i, l, r) for (int i = (l); i <= (r); ++i)
const int N = 5e5 + 5;
const ll P = 1e18;
int n, a[N];
__int128 hsh[N];
signed main() {
int t;
cin >> t;
while (t--) {
int k;
cin >> n >> k;
mt19937_64 rnd(time(0));
int ans=0;
map<int,int>rdm;
map<int, int> cnt;
map<__int128, int> mp;
for(int i=0;i<=n;i++)hsh[i]=0;
R(i, 1, n) {
hsh[i] = hsh[i - 1];
cin >> a[i];
if(rdm.count(a[i])==0)rdm[a[i]] = rnd() % P + 1;
hsh[i] -= 1ll * cnt[a[i]] * rdm[a[i]];
++cnt[a[i]];
cnt[a[i]] %= k;
hsh[i] += 1ll * cnt[a[i]] * rdm[a[i]];
}
mp[0] = 1;
map<int, int> cnt2;
for (int i = 1, j = 0; i <= n; ++i) {
++cnt2[a[i]];
while (cnt2[a[i]] > k) --cnt2[a[j]], (j ? --mp[hsh[j - 1]] : 1), ++j;
ans += mp[hsh[i]];
++mp[hsh[i]];
}
cout << ans << '\n';
}
return 0;
}
线段树维护区间加等差数列
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define Pair pair<LL, LL>
#define ls rt << 1
#define rs rt << 1 | 1
#define PI acos(-1.0)
#define eps 1e-13
#define mod 998244353
#define MAXN 50001
#define MS 100005
int n, m;
int a[MS];
struct node {
LL val;
LL la;
} p[MS << 2];
void push_up(int rt) {
p[rt].val = p[ls].val + p[rs].val;
}
void push_down(int rt, int l, int r) {
if (p[rt].la) {
int m = l + r >> 1;
p[ls].val += p[rt].la * (m - l + 1);
p[rs].val += p[rt].la * (r - m);
p[ls].la += p[rt].la;
p[rs].la += p[rt].la;
p[rt].la = 0;
}
}
void build(int l, int r, int rt) {
if (l == r) {
p[rt].val = a[l] - a[l - 1];
return;
}
int m = l + r >> 1;
build(l, m, ls);
build(m + 1, r, rs);
push_up(rt);
}
void modify(int L, int R, int l, int r, int rt, LL val) {
if (L <= l && r <= R) {
p[rt].val += val * (r - l + 1);
p[rt].la += val;
return;
}
int m = l + r >> 1;
push_down(rt, l, r);
if (m >= L)
modify(L, R, l, m, ls, val);
if (m < R)
modify(L, R, m + 1, r, rs, val);
push_up(rt);
}
LL query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return p[rt].val;
}
int m = l + r >> 1;
push_down(rt, l, r);
LL ans = 0;
if (m >= L)
ans += query(L, R, l, m, ls);
if (m < R)
ans += query(L, R, m + 1, r, rs);
return ans;
}
inline void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, n, 1);
while (m--) {
int op;
cin >> op;
if (op == 1) {
LL l, r, k, d;
cin >> l >> r >> k >> d;
modify(l, l, 1, n, 1, k);
if (l + 1 <= r)
modify(l + 1, r, 1, n, 1, d);
if (r + 1 <= n)
modify(r + 1, r + 1, 1, n, 1, -(d * (r - l) + k));
} else if (op == 2) {
int pos;
cin >> pos;
cout << query(1, pos, 1, n, 1) << "\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
// srand((unsigned)time(0));
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int ce = 1;
// cin >> ce;
// scanf("%d",&ce);
while (ce--) solve();
return 0;
}
/*
*/
线段树 3（区间最值操作、区间历史最值）
给出一个长度为 $n$ 的数列 $A$，同时定义一个辅助数组 $B$，$B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：
1 l r k：对于所有的 $i\in[l,r]$，将 $A_i$ 加上 $k$（$k$ 可以为负数）。2 l r v：对于所有的 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,v)$。3 l r：求 $\sum_{i=l}^{r}A_i$。4 l r：对于所有的 $i\in[l,r]$，求 $A_i$ 的最大值。5 l r：对于所有的 $i\in[l,r]$，求 $B_i$ 的最大值。
在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$。
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) 114514
#endif
using namespace std;
using LL = long long;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 1e9 + 7;
const int N = 3e5 + 10;
class LSGT {
public:
struct tag {
LL addmax, addmax_, add, add_;
tag() : addmax(0), addmax_(-INF), add(0), add_(-INF) {}
tag(LL add) : addmax(add), addmax_(add), add(add), add_(add) {}
tag(LL addmax, LL addmax_, LL add, LL add_) : addmax(addmax), addmax_(addmax_), add(add), add_(add_) {}
bool empty() const {
return addmax == 0 && addmax_ == -INF && add == 0 && add_ == -INF;
}
void apply(const tag &o) {
add_ = max(add_, add + o.add_);
addmax_ = max(addmax_, addmax + o.addmax_);
add += o.add;
addmax += o.addmax;
}
};
struct info {
LL cntM1, sum, M1, M2, len, b;
info() : cntM1(1), sum(0), M1(-INF), M2(-INF), len(1), b(0) {}
info(LL x) : cntM1(1), sum(x), M1(x), M2(-INF), len(1), b(x) {}
info(LL cntM1, LL sum, LL M1, LL M2, LL len, LL b) : cntM1(cntM1), sum(sum), M1(M1), M2(M2), len(len), b(b) {}
friend info operator+(const info &a, const info &b) {
info res;
res.len = a.len + b.len;
res.sum = a.sum + b.sum;
res.b = max(a.b, b.b);
if (a.M1 == b.M1) {
res.cntM1 = a.cntM1 + b.cntM1;
res.M1 = a.M1;
res.M2 = max(a.M2, b.M2);
} else if (a.M1 > b.M1) {
res.cntM1 = a.cntM1;
res.M1 = a.M1;
res.M2 = max(a.M2, b.M1);
} else {
res.cntM1 = b.cntM1;
res.M1 = b.M1;
res.M2 = max(b.M2, a.M1);
}
return res;
}
void apply(const tag &o) {
sum += o.add * len - o.add * cntM1 + o.addmax * cntM1;
b = max(b, M1 + o.addmax_);
M1 += o.addmax;
M2 += o.add;
}
};
private:
std::vector<info> node;
std::vector<tag> ta;
int siz;
void build(int idx, int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
build(idx << 1, l, mid), build(idx << 1 | 1, mid + 1, r);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
template <typename T>
void build(int idx, int l, int r, const std::vector<T> &vec) {
if (l == r) {
node[idx] = vec[l];
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid, vec), build(idx << 1 | 1, mid + 1, r, vec);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
void apply(int idx) {
if (ta[idx].empty())
return;
LL maxx = max(node[idx << 1].M1, node[idx << 1 | 1].M1);
if (node[idx << 1].M1 == maxx)
node[idx << 1].apply(ta[idx]), ta[idx << 1].apply(ta[idx]);
else
node[idx << 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_}), ta[idx << 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_});
if (node[idx << 1 | 1].M1 == maxx)
node[idx << 1 | 1].apply(ta[idx]), ta[idx << 1 | 1].apply(ta[idx]);
else
node[idx << 1 | 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_}), ta[idx << 1 | 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_});
ta[idx] = {};
}
void modify(int idx, int l, int r, int ql, int qr, tag add) {
if (add.add == 0 && add.addmax >= node[idx].M1)
return;
if (ql <= l && qr >= r && (add.add != 0 || add.addmax > node[idx].M2)) {
if (add.add == 0) {
add.addmax = -node[idx].M1 + add.addmax;
add.addmax_ = add.addmax;
}
ta[idx].apply(add);
node[idx].apply(add);
return;
}
apply(idx);
int mid = (l + r) >> 1;
if (ql <= mid)
modify(idx << 1, l, mid, ql, qr, add);
if (qr > mid)
modify(idx << 1 | 1, mid + 1, r, ql, qr, add);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
info query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r)
return node[idx];
apply(idx);
int mid = (l + r) >> 1;
if (qr <= mid)
return query(idx << 1, l, mid, ql, qr);
else if (ql > mid)
return query(idx << 1 | 1, mid + 1, r, ql, qr);
else
return query(idx << 1, l, mid, ql, qr) + query(idx << 1 | 1, mid + 1, r, ql, qr);
}
public:
LSGT(const int size) : node(size << 2), ta(size << 2), siz(size) {
build(1, 1, siz);
}
template <typename T>
LSGT(const std::vector<T> &vec) : node(vec.size() << 2), ta(vec.size() << 2), siz(vec.size() - 1) {
build(1, 1, siz, vec);
}
void modify(int ql, int qr, const tag &add) {
modify(1, 1, siz, ql, qr, add);
}
info query(int ql, int qr) {
return query(1, 1, siz, ql, qr);
}
};
void solve() {
int n, m;
cin >> n;
cin >> m;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
LSGT tr(arr);
while (m--) {
int op;
cin >> op;
int l, r;
cin >> l >> r;
if (op == 1) {
int x;
cin >> x;
if (x)
tr.modify(l, r, x);
} else if (op == 2) {
int x;
cin >> x;
tr.modify(l, r, {x, 0, 0, 0});
} else if (op == 3) {
cout << tr.query(l, r).sum << '\n';
} else if (op == 4) {
cout << tr.query(l, r).M1 << '\n';
} else if (op == 5) {
cout << tr.query(l, r).b << '\n';
}
}
}
signed main() {
#ifdef LOCAL
clock_t tttttttt = clock();
freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
//*****************************************************************
int t = 1;
// cin >> t;
while (t--) solve();
//*****************************************************************
#ifdef LOCAL
cerr << "Time Used: " << fixed << setprecision(3) << (clock() - tttttttt) / (CLOCKS_PER_SEC / 1000.0) << " ms" << endl;
#endif
return 0;
}
区间限制最大值最小值, 区间加, 查询区间最小值最大值,区间和
class LSGT {
public:
struct tag {
LL add, Min, Max;
tag() : add(0), Min(INF), Max(-INF) {}
tag(LL add) : add(add), Min(INF), Max(-INF) {}
tag(LL add, LL Min, LL Max) : add(add), Min(Min), Max(Max) {}
bool empty() const {
return add == 0 && Min == INF && Max == -INF;
}
void apply(const tag &o) {
add += o.add;
if (Min != INF)
Min += o.add;
if (Max != -INF)
Max += o.add;
if (Min <= o.Max) {
Min = Max = o.Max;
} else if (Max >= o.Min) {
Min = Max = o.Min;
} else {
Min = min(o.Min, Min);
Max = max(Max, o.Max);
}
}
};
struct info {
LL cntM1, sum, M1, M2, len, cntm1, m1, m2;
info() : cntM1(1), sum(0), M1(0), M2(-INF), len(1), cntm1(1), m1(0), m2(INF) {}
info(LL x) : cntM1(1), sum(x), M1(x), M2(-INF), len(1), cntm1(1), m1(x), m2(INF) {}
info(LL cntM1, LL sum, LL M1, LL M2, LL len, LL cntm1, LL m1, LL m2) : cntM1(cntM1), sum(sum), M1(M1), M2(M2), len(len), cntm1(cntm1), m1(m1), m2(m2) {}
friend info operator+(const info &a, const info &b) {
info res;
res.len = a.len + b.len;
res.sum = a.sum + b.sum;
if (a.M1 == b.M1) {
res.cntM1 = a.cntM1 + b.cntM1;
res.M1 = a.M1;
res.M2 = max(a.M2, b.M2);
} else if (a.M1 > b.M1) {
res.cntM1 = a.cntM1;
res.M1 = a.M1;
res.M2 = max(a.M2, b.M1);
} else {
res.cntM1 = b.cntM1;
res.M1 = b.M1;
res.M2 = max(b.M2, a.M1);
}
if (a.m1 == b.m1) {
res.cntm1 = a.cntm1 + b.cntm1;
res.m1 = a.m1;
res.m2 = min(a.m2, b.m2);
} else if (a.m1 < b.m1) {
res.cntm1 = a.cntm1;
res.m1 = a.m1;
res.m2 = min(a.m2, b.m1);
} else {
res.cntm1 = b.cntm1;
res.m1 = b.m1;
res.m2 = min(a.m1, b.m2);
}
return res;
}
void apply(const tag &o) {
sum += o.add * len;
M1 += o.add;
M2 += o.add;
m1 += o.add;
m2 += o.add;
if (M1 == m1) {
if (M1 > o.Min) {
sum -= (M1 - o.Min) * cntM1;
m1 = M1 = o.Min;
}
if (m1 < o.Max) {
sum -= (m1 - o.Max) * cntm1;
M1 = m1 = o.Max;
}
return;
}
if (o.Min == o.Max) {
sum = len * o.Min;
M1 = m1 = o.Min;
cntm1 = cntM1 = len;
return;
}
if (M1 > o.Min) {
sum -= (M1 - o.Min) * cntM1;
if (M1 == m2)
m2 = M1 = o.Min;
else
M1 = o.Min;
}
if (m1 < o.Max) {
sum -= (m1 - o.Max) * cntm1;
if (m1 == M2)
m1 = M2 = o.Max;
else
m1 = o.Max;
}
}
};
private:
std::vector<info> node;
std::vector<tag> ta;
int siz;
void build(int idx, int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
build(idx << 1, l, mid), build(idx << 1 | 1, mid + 1, r);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
template <typename T>
void build(int idx, int l, int r, const std::vector<T> &vec) {
if (l == r) {
node[idx] = vec[l];
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid, vec), build(idx << 1 | 1, mid + 1, r, vec);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
void apply(int idx) {
if (ta[idx].empty())
return;
ta[idx << 1].apply(ta[idx]);
ta[idx << 1 | 1].apply(ta[idx]);
node[idx << 1].apply(ta[idx]);
node[idx << 1 | 1].apply(ta[idx]);
ta[idx] = {};
}
void modify(int idx, int l, int r, int ql, int qr, const tag &add) {
if (!add.add && add.Min >= node[idx].M1 && add.Max <= node[idx].m1)
return;
if (ql <= l && qr >= r && add.Min > node[idx].M2 && add.Max < node[idx].m2) {
ta[idx].apply(add);
node[idx].apply(add);
return;
}
apply(idx);
int mid = (l + r) >> 1;
if (ql <= mid)
modify(idx << 1, l, mid, ql, qr, add);
if (qr > mid)
modify(idx << 1 | 1, mid + 1, r, ql, qr, add);
node[idx] = node[idx << 1] + node[idx << 1 | 1];
}
info query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r)
return node[idx];
apply(idx);
int mid = (l + r) >> 1;
if (qr <= mid)
return query(idx << 1, l, mid, ql, qr);
else if (ql > mid)
return query(idx << 1 | 1, mid + 1, r, ql, qr);
else
return query(idx << 1, l, mid, ql, qr) + query(idx << 1 | 1, mid + 1, r, ql, qr);
}
public:
LSGT(const int size) : node(size << 2), ta(size << 2), siz(size) {
build(1, 1, siz);
}
template <typename T>
LSGT(const std::vector<T> &vec) : node(vec.size() << 2), ta(vec.size() << 2), siz(vec.size() - 1) {
build(1, 1, siz, vec);
}
void modify(int ql, int qr, const tag &add) {
modify(1, 1, siz, ql, qr, add);
}
info query(int ql, int qr) {
return query(1, 1, siz, ql, qr);
}
};
void solve() {
int n, m;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i];
LSGT tr(arr);
cin >> m;
while (m--) {
int op;
cin >> op;
int l, r;
cin >> l >> r;
if (op == 1) {
int x;
cin >> x;
// 区间加 x
tr.modify(l, r, {x});
} else if (op == 2) {
int x;
cin >> x;
// 区间取max(x,a[i])
tr.modify(l, r, {0, INF, x});
} else if (op == 3) {
int x;
cin >> x;
// 区间取min(x,a[i])
tr.modify(l, r, {0, x, -INF});
} else if (op == 4) {
// 区间求和
cout << tr.query(l, r).sum << '\n';
} else if (op == 5) {
// 区间最大值
cout << tr.query(l, r).M1 << '\n';
} else if (op == 6) {
// 区间最小值
cout << tr.query(l, r).m1 << '\n';
}
}
}
signed main() {
#ifdef LOCAL
clock_t tttttttt = clock();
freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
//*****************************************************************
int t = 1;
// cin >> t;
while (t--) solve();
//*****************************************************************
#ifdef LOCAL
cerr << "Time Used: " << fixed << setprecision(3) << (clock() - tttttttt) / (CLOCKS_PER_SEC / 1000.0) << " ms" << endl;
#endif
return 0;
}
在线静态区间mex
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int tot = 0;
struct node {
int ls, rs;
int v;
} seg[N * 24];
int rt[N], a[N];
int n, m;
void pushup(int k)
{
seg[k].v = min(seg[seg[k].ls].v, seg[seg[k].rs].v);
}
int modify(int old, int l, int r, int pos, int v)
{
int p = ++tot;
seg[p] = seg[old];
if (l == r)
{
seg[p].v = v;
return p;
}
int mid = (l + r) >> 1;
if (pos <= mid)
seg[p].ls = modify(seg[old].ls, l, mid, pos, v);
else
seg[p].rs = modify(seg[old].rs, mid + 1, r, pos, v);
pushup(p);
return p;
}
int query(int p, int l, int r, int pos)
{
if (l == r)
{
return l;
}
int mid = (l + r) >> 1;
if (seg[seg[p].ls].v < pos)
return query(seg[p].ls, l, mid, pos);
else
return query(seg[p].rs, mid + 1, r, pos);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
rt[i] = modify(rt[i - 1], 0, n, a[i], i);
}
while (m--)
{
int l, r;
cin >> l >> r;
cout << query(rt[r], 0, n, l) << '\n';
}
}
单点修改区间颜色数:容易证明 k维莫队，块大小取$\frac{n}{m^\frac{1}{k}}$时时间复杂度最优。
#include <bits/stdc++.h>
using namespace std;
const int N = 133334;
struct Modify {
int pos, x; // a[pos] -> x
} M[N];
struct Query {
int l, r, t, idx;
};
char opt;
vector<Query> Q;
int n, m, q, t, l, r, a[N];
int cur, ans[N], cnt[1000010];
inline void optimizeIO(void) {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
}
inline void init(void) {
const int B = n / pow(m, 1.0 / 3);
sort(Q.begin(), Q.end(), [=](Query &x, Query &y) {
if (x.l / B != y.l / B) return x.l < y.l;
if (x.r / B != y.r / B) return x.r < y.r;
return (x.r / B) & 1 ? x.t < y.t : x.t > y.t;
});
}
inline void add(int val) {
if (cnt[val]++ == 0) ++cur;
}
inline void del(int val) {
if (--cnt[val] == 0) --cur;
}
inline void upd(int t, int l, int r) { // 维护由于时间造成的变化
if (l <= M[t].pos && M[t].pos <= r) {
del(a[M[t].pos]), add(M[t].x);
}
// 这是一个很巧妙的操作。
// 由于做完这次操作之后，再一次做这个操作一定是相反的操作，
// 所以可以直接交换当前位置的值和操作更改后的值。
swap(a[M[t].pos], M[t].x);
}
inline void MoAlgo(void) {
int l = 1, r = 0, t = 0; // 当前状态
for (int i = 0; i < q; i++) {
while (Q[i].l < l) add(a[--l]);
while (r < Q[i].r) add(a[++r]);
while (l < Q[i].l) del(a[l++]);
while (Q[i].r < r) del(a[r--]);
while (t < Q[i].t) upd(++t, l, r);
while (Q[i].t < t) upd(t--, l, r);
ans[Q[i].idx] = cur;
}
}
int main(int argc, char const *argv[]) {
optimizeIO(), cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
// q -> 询问的个数，等于 Q.size()
// t -> 当前时间戳
for (int i = 1; i <= m; i++) {
cin >> opt >> l >> r;
if (opt == 'R') M[++t] = {l, r};
else Q.push_back({l, r, t, ++q});
}
init(), MoAlgo();
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
dx实现
// 带修莫队 O(n^(5/3))
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1000005;
int n, m, B, mq, mr, a[N];
int sum, cnt[N], ans[N];
struct Q { // 询问
int l, r, id, tim;
// 按l/B、r/B和tim排序
bool operator<(Q &b) {
if (l / B != b.l / B)
return l < b.l;
if (r / B != b.r / B)
return r < b.r;
return tim < b.tim;
}
} q[N];
struct R { // 替换
int p, c;
} R[N];
void add(int x) {
if (!cnt[x])
sum++; // x第一次则累计
cnt[x]++; // x出现次数
}
void del(int x) {
cnt[x]--;
if (!cnt[x])
sum--;
}
int main() {
scanf("%d%d", &n, &m);
B = pow(n, 0.66);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) { // 操作
char c[2];
int l, r;
scanf("%s%d%d", c, &l, &r);
if (c[0] == 'Q')
q[++mq] = {l, r, mq, mr};
else
R[++mr] = {l, r};
}
sort(q + 1, q + 1 + mq);
for (int i = 1, l = 1, r = 0, x = 0; i <= mq; i++) {
while (l > q[i].l) add(a[--l]); // 左扩展
while (r < q[i].r) add(a[++r]); // 右扩展
while (l < q[i].l) del(a[l++]); // 左删除
while (r > q[i].r) del(a[r--]); // 右删除
while (x < q[i].tim) { // 时间戳变大，替换
int p = R[++x].p;
// 位置p介于[l,r]，先删旧数，后加新数
if (l <= p && p <= r)
del(a[p]), add(R[x].c);
swap(a[p], R[x].c); // 交换a,R的对应数
}
while (x > q[i].tim) { // 时间戳变小，还原
int p = R[x].p;
if (l <= p && p <= r)
del(a[p]), add(R[x].c);
swap(a[p], R[x--].c);
}
ans[q[i].id] = sum;
}
for (int i = 1; i <= mq; i++) printf("%d\n", ans[i]);
}
区间修改区间颜色数
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using ll = long long;
int n, QT, a[N], qt, rq, pr[N], mp[N], mt;
struct Q {
int l, r, d, p;
} q[N * 6], q2[N * 6];
struct odt {
int l, r;
mutable int d;
bool operator<(const odt &z)
const { return l < z.l; }
};
struct rag {
int l, r;
bool operator<(const rag &z)
const { return r < z.r; }
};
void addp(int x, int d) { q[++rq] = {pr[x], x, d}; }
void cgpr(int x, int y) {
if (pr[x] != y)
addp(x, -1), pr[x] = y, addp(x, 1);
}
struct RGdt : set<rag> {
void add(int l, int r) {
auto it = lower_bound({0, r});
if (it != end())
cgpr(it->l, r);
if (it != begin())
--it, cgpr(l, it->r);
else
cgpr(l, 0);
insert({l, r});
}
void del(int l, int r) {
erase({l, r});
auto it = lower_bound({0, r});
if (it != end()) {
if (it != begin()) {
auto at = it;
--at;
cgpr(it->l, at->r);
} else
cgpr(it->l, 0);
}
}
} lt[N];
struct Odt : set<odt> {
set<odt>::iterator split(int r) {
if (r > n)
return end();
auto it = lower_bound({r});
if (it != end() && it->l == r)
return it;
--it;
int L = it->l, R = it->r, D = it->d;
lt[D].erase({L, R}), lt[D].insert({L, r - 1});
lt[D].insert({r, R});
erase(it), insert({L, r - 1, D});
auto res = insert({r, R, D}).first;
return res;
}
} ADT;
ll ct[N], ans[N];
void solve(int l, int r) {
if (l >= r)
return;
int i, x, y, md = l + r >> 1;
solve(l, md), solve(md + 1, r);
for (x = md + 1, y = l; x <= r; ++x) {
while (y <= md && q[y].l <= q[x].l) {
if (!q[y].p)
for (i = q[y].r; i <= n; i += i & -i) ct[i] += q[y].d;
++y;
}
if (q[x].p)
for (i = q[x].r; i; i -= i & -i) ans[q[x].p] += q[x].d * ct[i];
}
for (x = l; x < y; ++x)
if (!q[x].p)
for (i = q[x].r; i <= n; i += i & -i) ct[i] -= q[x].d;
merge(q + l, q + md + 1, q + md + 1, q + r + 1, q2 + l, [&](Q x, Q y) {
return x.l < y.l;
});
for (i = l; i <= r; ++i) q[i] = q2[i];
}
int main() {
ios::sync_with_stdio(false);
int i, j, A, l, r, d, qi;
cin >> n >> QT;
for (i = 1; i <= n; ++i) cin >> a[i], mp[++mt] = a[i];
for (qi = 1; qi <= QT; ++qi) {
cin >> q2[qi].p >> q2[qi].l >> q2[qi].r;
if (q2[qi].p == 1) {
cin >> q2[qi].d;
mp[++mt] = q2[qi].d;
}
}
sort(mp + 1, mp + mt + 1), unique(mp + 1, mp + mt + 1) - mp - 1;
for (i = 1; i <= n; ++i) a[i] = lower_bound(mp + 1, mp + mt + 1, a[i]) - mp;
for (qi = 1; qi <= QT; ++qi)
if (q2[qi].p == 1)
q2[qi].d = lower_bound(mp + 1, mp + mt + 1, q2[qi].d) - mp;
for (i = 1; i <= n; ++i) {
ADT.insert({i, i, a[i]});
if (lt[a[i]].size()) {
auto it = lt[a[i]].end();
--it;
pr[i] = it->r;
}
lt[a[i]].insert({i, i});
addp(i, 1);
}
for (qi = 1; qi <= QT; ++qi) {
A = q2[qi].p, l = q2[qi].l, r = q2[qi].r, d = q2[qi].d;
if (A == 1) {
auto R = ADT.split(r + 1), L = ADT.split(l);
auto it = L;
lt[it->d].del(it->l, it->r);
for (++it; it != R; ++it) cgpr(it->l, it->l - 1), lt[it->d].del(it->l, it->r);
ADT.erase(L, R);
ADT.insert({l, r, d});
lt[d].add(l, r);
} else {
++qt, q[++rq] = {l - 1, r, 1, qt};
q[++rq] = {l - 1, l - 1, -1, qt};
}
}
solve(1, rq);
for (i = 1; i <= qt; ++i)
printf("%lld\n", ans[i]);
return 0;
}
给你一个数组${a_i}$支持两种操作：
1、查询区间$[l,r]$中每个数字出现次数的mex。
2、单点修改某一个位置的值。
mex指的是一些数字中最小的未出现的自然数。值得注意的是，因为 ${a_i}$ 是正整数，所以 $0$ 的出现次数为 $0$，即操作 $1$ 的答案不会是 $0$。
#include<bits/stdc++.h>
using namespace std;
struct Query {
int l, r, t, id;
};
struct Change {
int pos, v;
};
const int MAXN = 100000 * 2 + 5;
Query q[MAXN];
Change c[MAXN];
int v[MAXN], cnt[MAXN], tot[MAXN], ans[MAXN], a[MAXN];
int cntQ, cntC;
int n, m, t, siz, mex = 1;
bool cmp(Query& a, Query& b) {
if(a.l / t != b.l / t) {
return a.l < b.l;
}
if(a.r / t != b.r / t) {
return a.r < b.r;
}
return a.t < b.t;
}
void add(int x) {
tot[cnt[x]]--;
if(tot[cnt[x]] == 0) {
mex = min(mex, cnt[x]);
}
cnt[x]++;
tot[cnt[x]]++;
if(tot[cnt[x]] == 1 && mex == cnt[x]) {
for(int i = mex; i <= siz; i++) {
if(tot[i + 1] == 0) {
mex = i + 1;
break;
}
}
}
}
void del(int x) {
tot[cnt[x]]--;
if(tot[cnt[x]] == 0) {
mex = min(mex, cnt[x]);
}
cnt[x]--;
tot[cnt[x]]++;
if(tot[cnt[x]] == 1 && mex == cnt[x]) {
for(int i = mex; i <= siz; i++) {
if(tot[i + 1] == 0) {
mex = i + 1;
break;
}
}
}
}
void modify(int i, int t) {
if(q[i].l <= c[t].pos && c[t].pos <= q[i].r) {
del(a[c[t].pos]);
add(c[t].v);
}
swap(a[c[t].pos], c[t].v);
}
int main() {
scanf("%d%d", &n, &m);
t = pow(n, 2.0 / 3);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v[++siz] = a[i];
}
for(int i = 1; i <= m; i++) {
int op;
scanf("%d", &op);
if(op == 1) {
cntQ++;
scanf("%d%d", &q[cntQ].l, &q[cntQ].r);
q[cntQ].t = cntC;
q[cntQ].id = cntQ;
} else {
cntC++;
scanf("%d%d", &c[cntC].pos, &c[cntC].v);
v[++siz] = c[cntC].v;
}
}
sort(v + 1, v + siz + 1);
siz = unique(v + 1, v + siz + 1) - (v + 1);
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(v + 1, v + siz + 1, a[i]) - v;
}
for(int i = 1; i <= cntC; i++) {
c[i].v = lower_bound(v + 1, v + siz + 1, c[i].v) - v;
}
sort(q + 1, q + cntQ + 1, cmp);
int l = 1, r = 0, t = 0;
for(int i = 1; i <= cntQ; i++) {
while(l > q[i].l) add(a[--l]);
while(r < q[i].r) add(a[++r]);
while(l < q[i].l) del(a[l++]);
while(r > q[i].r) del(a[r--]);
while(t < q[i].t) modify(i, ++t);
while(t > q[i].t) modify(i, t--);
ans[q[i].id] = mex;
}
for(int i = 1; i <= cntQ; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
莫队：小z的袜子(区间内选到相同颜色的数的概率)
// 普通莫队 O(n*sqrt(n))
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 50005;
int n, m, B, a[N];
int sum, cnt[N], ans1[N], ans2[N];
struct Q {
int l, r, id;
// 按l所在块的编号l/B和r排序
bool operator<(const Q &x) const {
if (l / B != x.l / B)
return l < x.l;
if ((l / B) & 1)
return r < x.r;
return r > x.r;
}
} q[N];
void add(int x) {
sum += cnt[x]; // 当前x与前面每个x组合成双
cnt[x]++; // x的出现次数
}
void del(int x) {
cnt[x]--;
sum -= cnt[x];
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
scanf("%d%d", &n, &m);
B = sqrt(n); // 块的大小
for (int i = 1; i <= n; i++) // 颜色
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) // 询问
scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
sort(q + 1, q + m + 1);
for (int i = 1, l = 1, r = 0; i <= m; i++) {
if (q[i].l == q[i].r) {
ans1[q[i].id] = 0, ans2[q[i].id] = 1;
continue;
}
while (l > q[i].l) l--, add(a[l]); // 左扩展
while (r < q[i].r) r++, add(a[r]); // 右扩展
while (l < q[i].l) del(a[l]), l++; // 左删除
while (r > q[i].r) del(a[r]), r--; // 右删除
ans1[q[i].id] = sum;
ans2[q[i].id] = 1ll * (r - l + 1) * (r - l) / 2;
}
for (int i = 1; i <= m; i++) {
if (ans1[i]) {
int g = gcd(ans1[i], ans2[i]);
ans1[i] /= g, ans2[i] /= g; // 最简分数
} else
ans2[i] = 1;
printf("%d/%d\n", ans1[i], ans2[i]);
}
}
李超线段树
// 李超线段树 O(nlognlogn)
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const double eps = 1e-9;
const int N = 100005;
#define M1 39989
#define M2 1000000000
#define ls u << 1
#define rs u << 1 | 1
typedef pair<double, int> pdi;
int n, cnt, lastans;
struct line {
double k, b; // 斜率,截距
} p[N];
int tr[N << 2]; // 线段编号
int cmp(double a, double b) { // 比a,b
if (a - b > eps)
return 1;
if (b - a > eps)
return -1;
return 0;
}
double Y(int id, int x) { // 求Y值
return p[id].k * x + p[id].b;
}
void change(int u, int l, int r, int L, int R, int id) { // 修改
int mid = (l + r) >> 1;
if (L <= l && r <= R) {
int cm = cmp(Y(id, mid), Y(tr[u], mid));
if (cm == 1 || (!cm && id < tr[u]))
swap(id, tr[u]);
int cl = cmp(Y(id, l), Y(tr[u], l));
if (cl == 1 || (!cl && id < tr[u]))
change(ls, l, mid, L, R, id);
int cr = cmp(Y(id, r), Y(tr[u], r));
if (cr == 1 || (!cr && id < tr[u]))
change(rs, mid + 1, r, L, R, id);
return;
}
if (L <= mid)
change(ls, l, mid, L, R, id);
if (mid < R)
change(rs, mid + 1, r, L, R, id);
}
pdi pmax(pdi a, pdi b) { // Y值大且编号小
if (cmp(a.first, b.first) == 1)
return a;
else if (cmp(a.first, b.first) == -1)
return b;
else
return a.second < b.second ? a : b;
}
pdi query(int u, int l, int r, int x) { // 查询
if (l == r)
return {Y(tr[u], x), tr[u]};
int mid = (l + r) >> 1;
pdi t = {Y(tr[u], x), tr[u]};
if (x <= mid)
return pmax(t, query(ls, l, mid, x));
else
return pmax(t, query(rs, mid + 1, r, x));
}
int main() {
int op, x0, y0, x1, y1, x;
double k, b;
scanf("%d", &n);
while (n--) {
scanf("%d", &op);
if (op == 1) { // 插入一条线段
scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
x0 = (x0 + lastans - 1) % M1 + 1,
x1 = (x1 + lastans - 1) % M1 + 1;
y0 = (y0 + lastans - 1) % M2 + 1,
y1 = (y1 + lastans - 1) % M2 + 1;
if (x0 > x1)
swap(x0, x1), swap(y0, y1);
if (x0 == x1)
k = 0, b = max(y0, y1);
else
k = 1.0 * (y1 - y0) / (x1 - x0), b = y0 - k * x0;
p[++cnt] = {k, b};
change(1, 1, M1, x0, x1, cnt);
} else {
scanf("%d", &x); // 查询最大值
x = (x + lastans - 1) % M1 + 1;
lastans = query(1, 1, M1, x).second;
printf("%d\n", lastans);
}
}
}
李超树dp
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
const int N = 100005, M = 1000005;
ll h[N], s[N], k[N], b[N], f[N];
int n, tr[M << 2]; // 优势线段的编号
ll Y(int id, int x) { // 求Y值
return k[id] * x + b[id];
}
void change(int u, int l, int r, int id) { // 修改
int mid = l + r >> 1;
if (Y(id, mid) < Y(tr[u], mid))
swap(id, tr[u]);
if (Y(id, l) < Y(tr[u], l))
change(ls, l, mid, id);
if (Y(id, r) < Y(tr[u], r))
change(rs, mid + 1, r, id);
}
ll query(int u, int l, int r, int x) { // 查询
if (l == r)
return Y(tr[u], x);
int mid = l + r >> 1;
ll ans = Y(tr[u], x);
if (x <= mid)
return min(ans, query(ls, l, mid, x));
else
return min(ans, query(rs, mid + 1, r, x));
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", h + i);
for (int i = 1; i <= n; ++i) scanf("%lld", s + i), s[i] += s[i - 1];
k[0] = 0, b[0] = 1e18; // 第0条线段
k[1] = -2 * h[1];
b[1] = h[1] * h[1] - s[1];
change(1, 1, M, 1); // 插入第一条线段
for (int i = 2; i <= n; ++i) {
f[i] = h[i] * h[i] + s[i - 1] + query(1, 1, M, h[i]);
k[i] = -2 * h[i];
b[i] = f[i] + h[i] * h[i] - s[i];
change(1, 1, M, i);
}
printf("%lld", f[n]);
}
普通斜率优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 500010;
int n,m,q[N];
LL s[N],f[N];
LL dy(int i,int j){return f[i]+s[i]*s[i]-f[j]-s[j]*s[j];}
LL dx(int i,int j){return s[i]-s[j];}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)scanf("%lld",&s[i]),s[i]+=s[i-1];
int h=1,t=0;
for(int i=1;i<=n;i++){
while(h<t && dy(i-1,q[t])*dx(q[t],q[t-1])
<=dx(i-1,q[t])*dy(q[t],q[t-1])) t--;
q[++t]=i-1;
while(h<t && dy(q[h+1],q[h])
<=dx(q[h+1],q[h])*2*s[i]) h++;
int j=q[h];
f[i]=f[j]+(s[i]-s[j])*(s[i]-s[j])+m;
}
printf("%lld\n",f[n]);
}
}
单点修改，权值线段树合并
struct SegmentTree {
#define mid ((l + r) >> 1)
struct TREE {
int l, r;
int cnt;
} tr[N * 20]; /// 2nlogn
int tot;
void push_up(int cur) {
tr[cur].cnt = tr[tr[cur].l].cnt + tr[tr[cur].r].cnt;
}
void change(int &cur, int l, int r, int pos, int x) {
if (!cur)
cur = ++tot;
if (l == r) {
tr[cur].cnt = 1;
return;
}
if (pos <= mid)
change(tr[cur].l, l, mid, pos, x);
else
change(tr[cur].r, mid + 1, r, pos, x);
push_up(cur);
}
int merge(int a, int b, int l, int r) {
if (!a || !b)
return a | b;
if (l == r)
return tr[a].cnt ? a : b;
int cur = ++tot;
tr[cur].l = merge(tr[a].l, tr[b].l, l, mid);
tr[cur].r = merge(tr[a].r, tr[b].r, mid + 1, r);
push_up(cur);
return cur;
}
int query(int cur, int l, int r, int ql, int qr) {
if (!cur || ql < l || qr > r || ql > qr)
return 0;
if (l == ql && r == qr)
return tr[cur].cnt;
if (qr <= mid)
return query(tr[cur].l, l, mid, ql, qr);
else if (ql > mid)
return query(tr[cur].r, mid + 1, r, ql, qr);
return query(tr[cur].l, l, mid, ql, mid) + query(tr[cur].r, mid + 1, r, mid + 1, qr);
}
} seg;
楼房重建
// 线段树+递归合并 nlognlogn
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100005;
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
double mx[N << 2];
int sum[N << 2];
// mx:区间最大斜率, sum:区间可见楼房数
int dfs(int u, int l, int r, double mls) { // 求右分支sum
if (mx[u] <= mls)
return 0; // 剪枝
if (l == r)
return mx[u] > mls; // 叶子
if (mx[ls] <= mls)
return dfs(rs, mid + 1, r, mls);
else
return dfs(ls, l, mid, mls) + sum[u] - sum[ls];
}
void pushup(int u, int l, int r) { // 上传
mx[u] = max(mx[ls], mx[rs]);
sum[u] = sum[ls] + dfs(rs, mid + 1, r, mx[ls]);
}
void change(int u, int l, int r, int x, double v) { // 点修
if (l == r) {
mx[u] = v;
sum[u] = 1;
return;
}
if (x <= mid)
change(ls, l, mid, x, v);
else
change(rs, mid + 1, r, x, v);
pushup(u, l, r);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
change(1, 1, n, x, (double)y / x);
printf("%d\n", sum[1]);
}
}
势能线段树：区间开方
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100005;
#define LL long long
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
LL a[N];
LL sum[N << 2], mx[N << 2];
// sum:区间和，mx:区间最大
void pushup(int u) { // 上传
sum[u] = sum[ls] + sum[rs];
mx[u] = max(mx[ls], mx[rs]);
}
void build(int u, int l, int r) { // 建树
sum[u] = mx[u] = a[l];
if (l == r)
return;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void change(int u, int l, int r, int x, int y) { // 区修
if (mx[u] == 1)
return; // 优化
if (l == r) {
sum[u] = sqrt(sum[u]);
mx[u] = sqrt(mx[u]);
return;
}
if (x <= mid)
change(ls, l, mid, x, y);
if (y > mid)
change(rs, mid + 1, r, x, y);
pushup(u);
}
LL query(int u, int l, int r, int x, int y) { // 区查
if (x <= l && r <= y)
return sum[u];
LL s = 0;
if (x <= mid)
s += query(ls, l, mid, x, y);
if (y > mid)
s += query(rs, mid + 1, r, x, y);
return s;
}
int main() {
int n, m, opt, l, r;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
build(1, 1, n);
scanf("%d", &m);
while (m--) {
scanf("%d%d%d", &opt, &l, &r);
if (l > r)
swap(l, r);
if (opt == 0)
change(1, 1, n, l, r);
else
printf("%lld\n", query(1, 1, n, l, r));
}
return 0;
}
给出一个动态的区间，以及m*m次询问，每次询问给出一段区间 [l,r]，要求出这段区间中最大连续子段和
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
const int N = 500010;
int n, m, a[N];
struct Tree { // 线段树
int l, r;
// 区间和,最大左子段和,最大右子段和,最大子段和
int sum, lmx, rmx, mx;
} tr[N * 4];
void pushup(Tree &u, Tree l, Tree r) {
u.sum = l.sum + r.sum;
u.lmx = max(l.lmx, l.sum + r.lmx);
u.rmx = max(r.rmx, r.sum + l.rmx);
u.mx = max(max(l.mx, r.mx), l.rmx + r.lmx);
}
void build(int u, int l, int r) { // 建树
tr[u] = {l, r, a[r], a[r], a[r], a[r]};
if (l == r)
return;
int m = l + r >> 1;
build(ls, l, m);
build(rs, m + 1, r);
pushup(tr[u], tr[ls], tr[rs]);
}
void change(int u, int x, int v) { // 点修
if (tr[u].l == tr[u].r) {
tr[u] = {x, x, v, v, v, v};
return;
}
int m = tr[u].l + tr[u].r >> 1;
if (x <= m)
change(ls, x, v);
else
change(rs, x, v);
pushup(tr[u], tr[ls], tr[rs]);
}
Tree query(int u, int x, int y) { // 区查
if (x <= tr[u].l && tr[u].r <= y)
return tr[u];
int m = tr[u].l + tr[u].r >> 1;
if (y <= m)
return query(ls, x, y);
if (x > m)
return query(rs, x, y);
Tree T; // 开一个临时节点，存储拼凑结果
pushup(T, query(ls, x, m), query(rs, m + 1, y));
return T;
}
// Tree query(int u,int x,int y){ //区查
// if(x>tr[u].r||y<tr[u].l)
// return {tr[u].l,tr[u].r,0,-1e9,-1e9,-1e9};
// if(x<=tr[u].l && tr[u].r<=y) return tr[u];
// Tree T; //开一个临时节点，存储拼凑结果
// pushup(T,query(ls,x,y),query(rs,x,y));
// return T;
// }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
while (m--) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 1) {
if (x > y)
swap(x, y);
printf("%d\n", query(1, x, y).mx);
} else
change(1, x, y);
}
return 0;
}
0 l r把 $[l, r]$ 区间内的所有数全变成 $0$；1 l r把 $[l, r]$ 区间内的所有数全变成 $1$；2 l r把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$，把所有的 $1$ 变成 $0$；3 l r询问 $[l, r]$ 区间内总共有多少个 $1$；4 l r询问 $[l, r]$ 区间内最多有多少个连续的 $1$。
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
const int N = 100005;
int n, m, a[N];
struct tree {
int l, r;
int b, lb, rb, mb, c, lc, rc, mc;
int len, tag, rev;
} tr[N << 2];
// b:区间1的个数, c:区间0的个数
// lb:区间左起1的长度, lc:区间左起0的长度
// rb:区间右起1的长度, rc:区间右起0的长度
// mb:区间1的最长长度, mc:区间0的最长长度
// len:区间的长度
// tag:区间赋值标记,无标记:-1,有标记:0或1
// rev:区间取反标记,无标记: 0,有标记:1
void pushup(tree& u, tree l, tree r) { // 上传
u.b = l.b + r.b;
u.lb = l.c ? l.lb : l.b + r.lb;
u.rb = r.c ? r.rb : r.b + l.rb;
u.mb = max(max(l.mb, r.mb), l.rb + r.lb);
u.c = l.c + r.c;
u.lc = l.b ? l.lc : l.c + r.lc;
u.rc = r.b ? r.rc : r.c + l.rc;
u.mc = max(max(l.mc, r.mc), l.rc + r.lc);
}
void pd(int u, int opt) { // 操作区间
tree& t = tr[u];
if (opt == 0) { // 区间赋值为0
t.b = t.lb = t.rb = t.mb = 0;
t.c = t.lc = t.rc = t.mc = t.len;
t.tag = 0;
t.rev = 0;
}
if (opt == 1) { // 区间赋值为1
t.b = t.lb = t.rb = t.mb = t.len;
t.c = t.lc = t.rc = t.mc = 0;
t.tag = 1;
t.rev = 0;
}
if (opt == 2) { // 区间取反
swap(t.b, t.c);
swap(t.lb, t.lc);
swap(t.rb, t.rc);
swap(t.mb, t.mc);
t.rev ^= 1;
}
}
void pushdown(int u) { // 下传
tree& t = tr[u];
if (t.tag == 0)
pd(ls, 0), pd(rs, 0);
if (t.tag == 1)
pd(ls, 1), pd(rs, 1);
if (t.rev)
pd(ls, 2), pd(rs, 2);
t.tag = -1;
t.rev = 0;
}
void build(int u, int l, int r) { // 建树
int t = a[l];
tr[u] = {l, r, t, t, t, t,
t ^ 1, t ^ 1, t ^ 1, t ^ 1, r - l + 1, -1, 0};
if (l == r)
return;
int m = l + r >> 1;
build(ls, l, m);
build(rs, m + 1, r);
pushup(tr[u], tr[ls], tr[rs]);
}
void change(int u, int x, int y, int k) { // 区修
if (y < tr[u].l || tr[u].r < x)
return;
if (x <= tr[u].l && tr[u].r <= y) {
pd(u, k);
return;
}
pushdown(u);
change(ls, x, y, k);
change(rs, x, y, k);
pushup(tr[u], tr[ls], tr[rs]);
}
tree query(int u, int x, int y) { // 区查
if (x > tr[u].r || y < tr[u].l)
return {};
if (x <= tr[u].l && tr[u].r <= y)
return tr[u];
pushdown(u);
tree T; // 开一个临时节点，存储拼凑结果
pushup(T, query(ls, x, y), query(rs, x, y));
return T;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
++l, ++r;
if (opt < 3)
change(1, l, r, opt);
else {
tree t = query(1, l, r);
printf("%d\n", opt == 3 ? t.b : t.mb);
}
}
return 0;
}
静态区间第k小
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define N 200005
#define lc(x) tr[x].l
#define rc(x) tr[x].r
struct node{
int l,r,s; //s:节点值域中有多少个数
}tr[N*20];
int root[N],idx;
int n,m,a[N];
vector<int> b;
void build(int &x,int l,int r){
x=++idx;
if(l==r) return;
int m=l+r>>1;
build(lc(x),l,m);
build(rc(x),m+1,r);
}
void insert(int x,int &y,int l,int r,int k){
y=++idx; tr[y]=tr[x]; tr[y].s++;
if(l==r) return;
int m=l+r>>1;
if(k<=m) insert(lc(x),lc(y),l,m,k);
else insert(rc(x),rc(y),m+1,r,k);
}
int query(int x,int y,int l,int r,int k){
if(l==r) return l;
int m=l+r>>1;
int s=tr[lc(y)].s-tr[lc(x)].s;
if(k<=s) return query(lc(x),lc(y),l,m,k);
else return query(rc(x),rc(y),m+1,r,k-s);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]); b.push_back(a[i]);
}
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
int bn=b.size();
build(root[0],1,bn);
for(int i=1; i<=n; i++){
int id=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
insert(root[i-1],root[i],1,bn,id);
}
while(m--){
int l,r,k; scanf("%d%d%d",&l,&r,&k);
int id=query(root[l-1],root[r],1,bn,k)-1;
printf("%d\n",b[id]);
}
return 0;
}
权值线段树+离散化实现平衡树,需要动态地维护一个可重集合 $M$，并且提供以下操作：
- 向 $M$ 中插入一个数 $x$。
- 从 $M$ 中删除一个数 $x$（若有多个相同的数，应只删除一个）。
- 查询 $M$ 中有多少个数比 $x$ 小，并且将得到的答案加一。
- 查询如果将 $M$ 从小到大排列后，排名位于第 $x$ 位的数。
- 查询 $M$ 中 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
- 查询 $M$ 中 $x$ 的后继（后继定义为大于 $x$，且最小的数）。
对于操作 3,5,6，不保证当前可重集中存在数 $x$。
// 权值线段树+离散化 nlogn
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100005;
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
int n, m, id;
int opt[N], a[N], b[N];
// opt:操作序号 a:数x b:备份数组
int sum[N << 2]; // 区间数的出现次数之和
void pushup(int u) { // 上传
sum[u] = sum[ls] + sum[rs];
}
void change(int u, int l, int r, int x, int k) { // 插删即点修
if (l == r) {
sum[u] += k;
return;
}
if (x <= mid)
change(ls, l, mid, x, k);
else
change(rs, mid + 1, r, x, k);
pushup(u);
}
int q_rank(int u, int l, int r, int x, int y) { // 排名即前缀和
if (x <= l && r <= y)
return sum[u];
int s = 0;
if (x <= mid)
s += q_rank(ls, l, mid, x, y);
if (y > mid)
s += q_rank(rs, mid + 1, r, x, y);
return s;
}
int q_num(int u, int l, int r, int x) { // 排名x的数
if (l == r)
return l;
if (x <= sum[ls])
return q_num(ls, l, mid, x);
else
return q_num(rs, mid + 1, r, x - sum[ls]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &opt[i], &a[i]);
if (opt[i] != 4)
b[++m] = a[i]; // 备份
}
sort(b + 1, b + m + 1); // 排序
m = unique(b + 1, b + 1 + m) - b - 1; // 去重
for (int i = 1; i <= n; i++) {
if (opt[i] != 4)
id = lower_bound(b + 1, b + m + 1, a[i]) - b;
if (opt[i] == 1)
change(1, 1, m, id, 1); // 插入x
if (opt[i] == 2)
change(1, 1, m, id, -1); // 删除x
if (opt[i] == 3) // x的排名
printf("%d\n", id > 1 ? q_rank(1, 1, m, 1, id - 1) + 1 : 1);
if (opt[i] == 4) // 排名为x的数
printf("%d\n", b[q_num(1, 1, m, a[i])]);
if (opt[i] == 5) { // x的前驱
int rk = q_rank(1, 1, m, 1, id - 1);
printf("%d\n", b[q_num(1, 1, m, rk)]);
}
if (opt[i] == 6) { // x的后继
int rk = q_rank(1, 1, m, 1, id) + 1;
printf("%d\n", b[q_num(1, 1, m, rk)]);
}
}
}
动态区间第k小
给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$，需要支持两种操作：
Q l r k表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数C x y表示将 $a_x$ 改为 $y$
// 整体二分+树状数组 O(nlognlogV)
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 300005;
#define lowbit(x) (x & -x)
int n, m, a[N], ans[N];
struct Q {
// 查询: [x,y]第k小，id编号，opt=1
// 原数: x位置，y值，opt=0
int x, y, k, id, opt;
};
vector<Q> q; // 数据序列
struct BIT {
vector<int> s;
void init(int n) { s.resize(n); }
void add(int x, int k) {
while (x <= n) s[x] += k, x += lowbit(x);
}
int sum(int x) {
int t = 0;
while (x) t += s[x], x -= lowbit(x);
return t;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
} tree; // 树状数组
void solve(vector<Q> q, int L, int R) {
if (!q.size())
return;
if (L == R) {
for (auto i : q)
if (i.opt)
ans[i.id] = L;
return;
}
int mid = L + R >> 1;
vector<Q> q1, q2;
for (auto i : q) {
if (!i.opt) { // 若是原数，按值分流
if (i.y <= mid)
tree.add(i.x, i.k), // 加入贡献
q1.push_back(i); // 分流到左边
else
q2.push_back(i); // 分流到右边
} else { // 若是查询，按个数分流
int s = tree.sum(i.x, i.y);
if (s >= i.k)
q1.push_back(i); // 分流到左边
else
i.k -= s, q2.push_back(i); // 分流到右边
}
}
for (auto i : q1)
if (!i.opt)
tree.add(i.x, -i.k); // 减去贡献
solve(q1, L, mid);
solve(q2, mid + 1, R); // 分治
}
int main() {
scanf("%d%d", &n, &m);
char ch[2];
int x, y, k;
tree.init(n + 1);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), q.push_back({i, a[i], 1, 0, 0});
for (int i = 1; i <= m; i++) {
scanf("%s%d%d", ch, &x, &y);
if (ch[0] == 'C')
q.push_back({x, a[x], -1, 0, 0}), // 旧数贡献-1
q.push_back({x, a[x] = y, 1, 0, 0}); // 新数贡献+1
else
scanf("%d", &k), q.push_back({x, y, k, i, 1});
}
memset(ans, -1, sizeof ans);
solve(q, 0, 1e9); // 整体二分
for (int i = 1; i <= m; i++)
if (~ans[i])
printf("%d\n", ans[i]);
}
线段树优化建图
const int MAXN = 5e5 + 5;
const int D = 5e5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, s;
int id[MAXN];
int dis[MAXN << 1];
vector<pair<int, int>> g[MAXN << 1];
void build(int x, int l, int r) {
if (l == r) {
id[l] = x;
return;
}
int mid = l + r >> 1;
g[x].push_back({x << 1, 0});
g[x].push_back({x << 1 | 1, 0});
g[(x << 1) + D].push_back({x + D, 0});
g[(x << 1 | 1) + D].push_back({x + D, 0});
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
void add(int x, int l, int r, int L, int R, int v, int w, int op) {
if (L <= l && r <= R) {
if (op)
g[v].push_back({x, w});
else
g[x + D].push_back({v, w});
return;
}
int mid = l + r >> 1;
if (L <= mid) add(x << 1, l, mid, L, R, v, w, op);
if (R > mid) add(x << 1 | 1, mid + 1, r, L, R, v, w, op);
}
void dijkstra(int s) {
vector<int> vis(MAXN * 2, 0);
priority_queue<pair<int, int>> q;
memset(dis, INF, sizeof(dis));
dis[s] = 0;
q.push({0, s});
while (!q.empty()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [y, w] : g[x]) {
dis[y] = min(dis[y], dis[x] + w);
q.push({-dis[y], y});
}
}
}
// op 1 : v->u 单向边
// op 2 : v->[l,r]
// op 3 :[l,r]-> v
void solve() {
cin >> n >> m >> s;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
int x = id[i];
g[x].push_back({x + D, 0});
g[x + D].push_back({x, 0});
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int v, u, w;
cin >> v >> u >> w;
g[id[v]].push_back({id[u], w});
} else if (op == 2) {
int v, l, r, w;
cin >> v >> l >> r >> w;
add(1, 1, n, l, r, id[v], w, 1);
} else {
int v, l, r, w;
cin >> v >> l >> r >> w;
add(1, 1, n, l, r, id[v], w, 0);
}
}
dijkstra(id[s]);
for (int i = 1; i <= n; i++) {
if (dis[id[i]] == INF)
cout << "-1 ";
else
cout << dis[id[i]] << ' ';
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！