答辩题做累了，做点轻松愉快的数据结构
排序
https://www.luogu.com.cn/problem/P2824
给定排列 \(a_{1\cdots n}\)，维护 \(m\) 次操作，形如：
0/1 l r，将 \(a_{l\cdots r}\) 按升序 / 降序排列。最后给定一个 \(p\)，问最终 \(a_p\) 的值。
\(n,m\le 10^5\)。
发现问题是类静态的，考虑离线做法。
在线做法放到后面的在线题目再讲，原因：在线做法 too dirty，杀鸡焉用牛刀。
发现如果值域为 \(\{0, 1\}\)，那么这样的排序是很简单的，直接统计区间内 0/1 个数然后推平即可。
这种转化后为 0/1 的情况，很容易想到二分答案：把 \(\le mid\) 的元素赋为 \(0\)，\(>mid\) 的元素赋为 \(1\) 即可 \(O(n\log^2 n)\) 解决问题。
推平时操作区间长可能为 \(0\)，不判掉这个会 RE
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
struct { int l, r, u, d; } t[maxn << 2];
int a[maxn];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
return;
}
void pushdown(int p) {
if (~t[p].d) {
t[lt].d = t[rt].d = t[p].d;
t[lt].u = (t[lt].r - t[lt].l + 1) * t[p].d;
t[rt].u = (t[rt].r - t[rt].l + 1) * t[p].d;
t[p].d = -1;
}
return;
}
void bld(int p, int l, int r, int k) {
t[p].l = l, t[p].r = r;
t[p].d = -1;
if (l == r) {
t[p].u = (a[l] >= k);
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid, k);
bld(rt, mid + 1, r, k);
pushup(p);
return;
}
void upd(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d = v;
t[p].u = (t[p].r - t[p].l + 1) * v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r, v);
if (r > mid)
upd(rt, l, r, v);
pushup(p);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = 0;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::tuple<int, int, int> > q(m);;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 0, op, l, r; i < m; ++i) {
std::cin >> op >> l >> r;
q[i] = { op, l, r };
}
int p;
std::cin >> p;
auto check = [&](int mid) {
bld(1, 1, n, mid);
for (int i = 0; i < m; ++i) {
auto &[op, l, r] = q[i];
int t = ask(1, l, r);
if (op == 0) {
t = (r - l + 1) - t;
if (t >= 1)
upd(1, l, l + t - 1, 0);
if (l + t <= r)
upd(1, l + t, r, 1);
}
else {
if (t >= 1)
upd(1, l, l + t - 1, 1);
if (l + t <= r)
upd(1, l + t, r, 0);
}
}
return ask(1, p, p);
};
int res = -1;
for (int l = 1, r = n, mid; l <= r; ) {
mid = (l + r) >> 1;
if (check(mid))
res = mid, l = mid + 1;
else
r = mid - 1;
}
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}Range Sort Query
https://www.luogu.com.cn/problem/AT_abc237_g
给定排列 \(a_{1\cdots n}\)，维护 \(m\) 次操作，形如：
0/1 l r，将 \(a_{l\cdots r}\) 按升序 / 降序排列。最后给定一个 \(x\)，求满足 \(a_p=x\) 的 \(p\)。
\(n,m\le 2\times 10^5\)。
发现这个问题不可二分，但根据 \(x\) 设 0/1 的想法显然可以沿用。
有一个形似等差子序列的想法：
发现对于 \(x\)，它是 0 或 1 无所谓，且两种设法中，被影响到的只有 \(x\) 这个值。
故对于两种设法分别做一次，最后不同的位置即为 \(p\)。
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
struct { int l, r, u, d; } t[maxn << 2];
int a[maxn];
#define lt (p << 1)
#define rt (lt | 1)
void pushup(int p) {
t[p].u = t[lt].u + t[rt].u;
return;
}
void pushdown(int p) {
if (~t[p].d) {
t[lt].d = t[rt].d = t[p].d;
t[lt].u = (t[lt].r - t[lt].l + 1) * t[p].d;
t[rt].u = (t[rt].r - t[rt].l + 1) * t[p].d;
t[p].d = -1;
}
return;
}
void bld(int p, int l, int r, int k) {
t[p].l = l, t[p].r = r;
t[p].d = -1;
if (l == r) {
t[p].u = (a[l] >= k);
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid, k);
bld(rt, mid + 1, r, k);
pushup(p);
return;
}
void upd(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d = v;
t[p].u = (t[p].r - t[p].l + 1) * v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
upd(lt, l, r, v);
if (r > mid)
upd(rt, l, r, v);
pushup(p);
return;
}
int ask(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].u;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = 0;
if (l <= mid)
res = ask(lt, l, r);
if (r > mid)
res += ask(rt, l, r);
return res;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m, k;
std::cin >> n >> m >> k;
std::vector<int> b(n + 1);
std::vector<std::tuple<int, int, int> > q(m);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
bld(1, 1, n, k + 1);
for (int i = 0, op, l, r; i < m; ++i) {
std::cin >> op >> l >> r;
q[i] = { op, l, r };
int t = ask(1, l, r);
if (op == 1) {
t = (r - l + 1) - t;
if (t >= 1)
upd(1, l, l + t - 1, 0);
if (l + t <= r)
upd(1, l + t, r, 1);
}
else {
if (t >= 1)
upd(1, l, l + t - 1, 1);
if (l + t <= r)
upd(1, l + t, r, 0);
}
}
for (int i = 1; i <= n; ++i)
b[i] = ask(1, i, i);
bld(1, 1, n, k);
for (auto &[op, l, r] : q) {
int t = ask(1, l, r);
if (op == 1) {
t = (r - l + 1) - t;
if (t >= 1)
upd(1, l, l + t - 1, 0);
if (l + t <= r)
upd(1, l + t, r, 1);
}
else {
if (t >= 1)
upd(1, l, l + t - 1, 1);
if (l + t <= r)
upd(1, l + t, r, 0);
}
}
for (int i = 1; i <= n; ++i)
if (ask(1, i, i) != b[i]) {
std::cout << i << '\n';
break;
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A Simple Task
https://www.luogu.com.cn/problem/CF558E
给定字符串 \(s_{1\cdots n}\)，维护 \(m\) 次操作，形如：
0/1 l r，将 \(s_{l\cdots r}\) 按升序 / 降序排列。输出所有操作后的 \(s\)。
\(n\le 10^5, m\le 5\times 10^4\)，\(s\) 由小写字母组成。
发现需要全局查询，上面设 0/1 的套路无法沿用
但发现这题本身值域就很小
所以只需要开 26 个线段树，暴力按
a ~ z排序，做区间覆盖即可。询问带 26 倍常数，故 \(m\) 会比 \(n\) 小。
From one to six
https://vjudge.net/problem/Gym-104254I#author=GPT_zh
给定序列 \(a_{1\cdots n}\)，只包含 \(1,2,3,4,5,6\)，维护 \(m\) 次操作，形如：
1 l r，将 \(a_{l\cdots r}\) 升序排列。2 l r，输出 \([l, r]\) 内的 LIS。最后给定一个 \(x\)，求满足 \(a_p=x\) 的 \(p\)。
\(n,m\le 2\times 10^5\)。
和上一题相似的，只需需要额外开一个新线段树记录当前的 \(a\)，同样只需区间覆盖即可。
转移直接套用朴素 LIS 的 DP 方式，很容易维护。
Philosopher
给定 \(a_{1\cdots n}\)，维护 \(m\) 次操作，形如：
1 l r 0/1，将 \(a_{l\cdots r}\) 按升序 / 降序排列。2 l r，询问区间内元素和。\(1\le n,m\le 2\times 10^5,V=10^9\)。
在线区间排序的通解：用若干个权值线段树维护连续段（递增 / 递减）。外层用一个同样支持分裂 & 合并 & reverse 的结构，fhq，又一个线段树什么的，记录权值线段树的分布情况及增减状态，以及每个树的元素和。
这样查询时就可以通过类似分块的方法求解。
一次排序，线段树分裂 + 线段树合并。一次操作中的分裂至多增加 2 势能，合并至少减少 1 势能。线段树分裂 & 合并均摊单 log，故总复杂度单 log。
为何内层不用 fhq？不经过特殊处理的 fhq 在有交合并时带两只 log。
Point Set Range Sort Range Composite
https://vjudge.net/problem/Yosupo-point_set_range_sort_range_composite#author=GPT_zh
给定 \(n\) 个二元组，由函数 \(f_{1\cdots n}=k_i\cdot x+b_i\) 和排序权值 \(p_{1\cdots n}\) 组成，维护 \(m\) 次操作，形如：
0 i p k b，修改当前的第 \(i\) 个元素的 \(f_i\) 和 \(p_i\)。1 l r x，询问 \(f_{r-1}(f_{r-2}(\cdots f_l(x)))\bmod 998244353\)。2/3 l r，将当前第 \(l\sim r\) 个元素按照 \(p\) 值升序 / 降序排列。\(1\le n,m\le 10^5,V=10^9\)。保证任意时刻，每个 \(p_i\) 互不相同。
- 和上一题没什么本质区别，换成了维护矩阵而已。额外注意矩阵 + reverse 的那些东西即可。
齐齐排序
https://ac.nowcoder.com/acm/problem/21439
给定序列 \(a_{1\cdots n}\)，维护 \(m\) 次操作，形如：
0 x，将 \(a_{1\cdots x}\) 按降序排列。
1 x，将 \(a_{1\cdots x}\) 按升序排列。输出操作完成后的序列。
\(n,m\le 2\times 10^5,V=10^9\)。
诈骗题
发现只存在前缀操作，显然 \(x\) 较大的会覆盖 \(x\) 较小的操作
容易发现有效操作的 \(x\) 形成一个后缀最大值序列。用这些操作给数打升序 / 降序标记。
先填完没有被操作过的位置（显然这样的位置在序列末），然后用一个
multiset装剩下所有数。倒序遍历还未填的位置，若这个位置上的标记是升序，则填最大值；否则填最小值。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::pair<int, int> > q(m + 1);
for (int i = 1; i <= m; ++i)
std::cin >> q[i].first >> q[i].second;
int mx = 0;
std::vector<int> tag(n + 1);
for (int i = m; i; --i)
if (q[i].second > mx) {
mx = q[i].second;
tag[q[i].second] = q[i].first;
}
std::multiset<int> t;
for (int i = 1; i <= mx; ++i)
t.insert(a[i]);
for (int i = mx, st = 0; i; --i) {
if (tag[i])
st = tag[i];
if (st == 1)
a[i] = *--t.end(), t.erase(--t.end());
else
a[i] = *t.begin(), t.erase(t.begin());
}
for (int i = 1; i <= n; ++i)
std::cout << a[i] << ' ';
std::cout << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}정렬 게임
https://vjudge.net/problem/Baekjoon-13415#author=GPT_zh
给定序列 \(a_{1\cdots n}\)，维护 \(m\) 次操作，形如：
x y，将 \(a_{1\cdots x}\) 按升序排列，接着，对 \(a_{1\cdots y}\) 按降序排列。输出操作完成后的序列。
\(n,m\le 10^5,|V|=10^4\)。
- 发现这个题严格弱于上一个题，没啥说的。
入れ替えと並び替え
https://www.luogu.com.cn/problem/AT_past202005_n
给定序列 \(a_{1\cdots n}\)，初始为 \(1,2,\cdots,n\)，维护 \(m\) 次操作，形如：
0 x，交换 \(a_x\) 与 \(a_{x+1}\)。
1 l r，将 \(a_{l\cdots r}\) 按升序排列。输出操作完成后的序列。
\(n,m\le 2\times 10^5\)。
诈骗题⨉2
初始是有序的，保证了仅需要复原被打乱的项即可完成排序。
维护每次交换在 \((x-1,x)\)、\((x,x+1)\)、\((x+1,x+2)\) 三个位置创建 / 删除的逆序对。
手玩发现操作给出的交换和目的为复原的交换都有可能带来新的逆序对。考虑势能分析。
操作给出的交换至多增加一个逆序对（势能），而一次目的为复原的交换至少减少一个逆序对（势能）。
故直接暴力复原范围内逆序对，复杂度 \(O(Q\log Q)\)。
双向排序
https://www.luogu.com.cn/problem/P8747
给定排列 \(a_{1\cdots n}\)，初始为 \(1,2,\cdots,n\)，维护 \(m\) 次操作，形如：
0 x，将 \(a_{1\cdots x}\) 按降序排列。
1 x，将 \(a_{x\cdots n}\) 按升序排列。输出操作完成后的序列。
\(n,m\le 2\times 10^5\)。
发现题目给的限制非常有意思，保证了最终序列一定满足前半截降序，后半截升序。
需要发现一个可怕的事实：操作相当于选取分割点 \(pos\) 左 / 右侧最小的数并挪到对侧。
维护每个点的 0/1 状态，线段树上二分并区间推平即可。
另一个很强的线性做法：只维护 \(pos\) 左边的点值，那么操作可以看作：
加入若干个最小的、不存在于左边的点 / 删除若干个存在于左边，且最小的点
用栈维护左边从小到大的所有连续段，每次加点暴力合并，删点则暴力删
发现加点只会增加最多一个连续段，且枚举连续段合并之后会减少对应的势能；删点同理。
故均摊线性。
