信息转化为主
B - Into Blocks (hard version)
https://www.luogu.com.cn/problem/CF1209G2
- trick：考察每个颜色出现的区间 \([s_{col},t_{col}]\)，对每个 \([s_{col},t_{col})\) 打标记，则没有被打过标记的点后能够进行一次分段。
对于每一段，其代价为段长度 - 众数出现次数。
这个众数乍一看有点吓人，实际上发现由于每个元素出现的所有位置都在这个段里，所以可以记录每个元素的个数，对于每个元素只钦定其中一个位置来记录即可快速维护。- 发现线段树能够比较容易地维护全局查询：维护 \(0\) 位置是经典 trick；且容易发现『段长』之和为 \(n\)，故只需维护众数。
实现技巧：单点本身就是自己的最小值，从这一点出发可以规避很多边界情况。
#include <bits/stdc++.h>
const int lim = 2e5;
const int maxn = 2e5 + 5;
struct node {
int l, r, u, d;
int lu, ru, mn, mx;
node operator+ (const node &q) const {
node res;
res.d = 0;
res.l = l, res.r = q.r;
res.mx = std::max(mx, q.mx);
res.mn = std::min(mn, q.mn);
if (mn < q.mn) {
res.mn = mn, res.u = u;
res.lu = lu, res.ru = std::max(q.mx, ru);
}
else if (q.mn < mn) {
res.mn = q.mn, res.u = q.u;
res.lu = std::max(mx, q.lu), res.ru = q.ru;
}
else {
res.lu = lu, res.ru = q.ru;
res.u = u + q.u + std::max(ru, q.lu);
}
return res;
}
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushval(int p, int d) {
t[p].mn += d, t[p].d += d;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = 0;
return;
}
void upd(int p, int x, int v) {
if (t[p].l == t[p].r) {
t[p].u = t[p].mx = v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid)
upd(lt, x, v);
else
upd(rt, x, v);
t[p] = t[lt] + t[rt];
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p] = t[lt] + t[rt];
return;
}
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, q;
std::cin >> n >> q;
std::vector<int> a(n + 1);
std::vector<std::set<int> > st(lim + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
st[a[i]].emplace(i);
}
bld(1, 1, n);
for (int i = 1; i <= lim; ++i)
if (!st[i].empty()) {
int s = *st[i].begin(), t = *--st[i].end();
if (s <= t - 1)
add(1, s, t - 1, 1);
upd(1, s, (int)st[i].size());
}
std::cout << n - ::t[1].u - ::t[1].lu - ::t[1].ru << '\n';
auto work = [&](int v, int k) {
if (st[v].empty())
return;
int s = *st[v].begin(), t = *--st[v].end();
if (s <= t - 1)
add(1, s, t - 1, k);
upd(1, s, k == 1 ? (int)st[v].size() : 0);
return;
};
for (int i, x; q--; ) {
std::cin >> i >> x;
work(a[i], -1), st[a[i]].erase(i), work(a[i], 1);
a[i] = x;
work(a[i], -1), st[a[i]].insert(i), work(a[i], 1);
std::cout << n - ::t[1].u - ::t[1].lu - ::t[1].ru << '\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;
}C - seats 排座位
https://www.luogu.com.cn/problem/P4898
很有价值的一个题
对于一个固定的 \(k\)，考虑怎么刻画合法矩形
发现『前 \(k\) 个元素构成矩形』比『大小为 \(k\) 的矩形包含前 \(k\) 个元素』更合理
考虑前 \(k\) 个元素在满足什么条件时构成矩形
我最开始的想法是『记录这 \(k\) 个元素占据的最大、最小、最左、最右，如果乘起来为 \(k\)，那么合法』
但会发现这个转化是不好做的，或者说就又往上面那个错误的判定转化（大小为 \(k\) 的矩形包含前 \(k\) 个元素）靠了。两个都有一个共同的问题，就是过于依赖这个 \(k\)，限制太具体了，导致不能很好地应用到每个 \(k\)
现在这个判定的转化比较合理的地方就在于，对矩形本身不存在约束，只是要求构成矩形。这样就允许直接从图形出发，更多地考虑怎样用单点信息合并出矩形与否
把 \([0,k)\) 染成黑色，其他为白色，那么有一个粗暴但简单的方法来刻画『矩形』这个要求：
图形存在四个『角』。
再刻画一下『角』：黑点左上 / 左下 / 右上 / 右下两个点都为白。
当然这样是很荒谬的，因为下图显然不只有四个角。
所以我们不得不把一个凹角也算作角，不难发现把上方凸角的定义中的主体换成白点即可定义凹角。
优化：算贡献
维护当前时刻，所有 \(4nm\) 个角在 \(k\) 处是否存在
此时要用一个类似维护 \(0\) 个数的方法来维护有 \(4\) 个角个数的 \(k\) 个数。
考虑这么一个可能的角：
其存在当且仅当 \(A\) 为黑，\(B,C\) 为白（凸角），或 \(A\) 为白，\(B,C\) 为黑（凹角）。
考察 \(A,B,C\) 第一次变黑的时间 \(k_A,k_B,k_C\)，那么 \(A\) 能够对所有 \(k\in[k_A,\min\{k_B,k_C\})\) 和 \(k\in[\max\{k_B,k_C\},k_A)\) 造成贡献。
- 每次修改只会做 \(O(1)\) 次区间加，是可维护的。注意两个被交换的点可能会有公共的相邻点，需要特别处理一下。
这个东西本质上可以看作一个 2⨉2 的Soble 算子，所以可以抠出来一般定义上的角
non-interactive version:
#include <bits/stdc++.h>
const int dir[][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
const int maxn = 1e6 + 5;
struct node {
int l, r, u, d, mn;
node operator+ (const node &q) const {
node res;
res.l = l, res.r = q.r, res.d = 0;
res.mn = std::min(mn, q.mn), res.u = 0;
if (mn == res.mn)
res.u = u;
if (q.mn == res.mn)
res.u += q.u;
return res;
}
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].u = r - l + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushval(int p, int v) {
t[p].mn += v, t[p].d += v;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = 0;
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p] = t[lt] + t[rt];
return;
}
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, q;
std::cin >> n >> m >> q;
const int N = n * m;
std::vector<std::pair<int, int> > pos(N + 1);
std::vector<std::vector<int> > id(n + 2, std::vector<int> (m + 2, N + 1));
for (int i = 1, x, y; i <= N; ++i) {
std::cin >> x >> y, ++x, ++y;
id[x][y] = i, pos[i] = { x, y };
}
bld(1, 1, N);
auto work = [&](int x, int y, int k) {
for (int i = 0; i < 2; ++i)
for (int j = 2; j < 4; ++j) {
int x1 = x + dir[j][0], y1 = y + dir[i][1];
if (id[x][y] < std::min(id[x1][y], id[x][y1]))
add(1, id[x][y], std::min(id[x1][y], id[x][y1]) - 1, k);
if (std::max(id[x1][y], id[x][y1]) < id[x][y])
add(1, std::max(id[x1][y], id[x][y1]), id[x][y] - 1, k);
}
return;
};
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
work(i, j, 1);
for (int i1, i2; q--; ) {
std::cin >> i1 >> i2, ++i1, ++i2;
auto [x1, y1] = pos[i1];
auto [x2, y2] = pos[i2];
std::set<std::pair<int, int> > st;
st.emplace(x1, y1);
for (auto [fx, fy] : dir) {
int x = x1 + fx, y = y1 + fy;
if (x >= 1 && x <= n && y >= 1 && y <= m)
st.emplace(x, y);
}
st.emplace(x2, y2);
for (auto [fx, fy] : dir) {
int x = x2 + fx, y = y2 + fy;
if (x >= 1 && x <= n && y >= 1 && y <= m)
st.emplace(x, y);
}
for (auto [x, y] : st)
work(x, y, -1);
std::swap(id[x1][y1], id[x2][y2]), std::swap(pos[i1], pos[i2]);
for (auto [x, y] : st)
work(x, y, 1);
std::cout << t[1].u << '\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;
}interactive version:
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#include "seats.h"
#endif
const int dir[][2] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
const int maxn = 1e6 + 5;
struct node {
int l, r, u, d, mn;
node operator+ (const node &q) const {
node res;
res.l = l, res.r = q.r, res.d = 0;
res.mn = std::min(mn, q.mn), res.u = 0;
if (mn == res.mn)
res.u = u;
if (q.mn == res.mn)
res.u += q.u;
return res;
}
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].u = r - l + 1;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushval(int p, int v) {
t[p].mn += v, t[p].d += v;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = 0;
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p] = t[lt] + t[rt];
return;
}
int n, m, N;
std::vector<std::pair<int, int> > pos;
std::vector<std::vector<int> > id(n + 2, std::vector<int> (m + 2, N + 1));
void work(int x, int y, int k) {
for (int i = 0; i < 2; ++i)
for (int j = 2; j < 4; ++j) {
int x1 = x + dir[j][0], y1 = y + dir[i][1];
if (id[x][y] < std::min(id[x1][y], id[x][y1]))
add(1, id[x][y], std::min(id[x1][y], id[x][y1]) - 1, k);
if (std::max(id[x1][y], id[x][y1]) < id[x][y])
add(1, std::max(id[x1][y], id[x][y1]), id[x][y] - 1, k);
}
return;
};
void give_initial_chart(int n, int m, std::vector<int> R, std::vector<int> C) {
::n = n, ::m = m, N = n * m;
pos.resize(N + 1);
id.assign(n + 2, std::vector<int> (m + 2, N + 1));
for (int i = 0; i < N; ++i) {
int x = R[i] + 1, y = C[i] + 1;
id[x][y] = i + 1, pos[i + 1] = { x, y };
}
bld(1, 1, N);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
work(i, j, 1);
return;
}
int swap_seats(int i1, int i2) {
++i1, ++i2;
auto [x1, y1] = pos[i1];
auto [x2, y2] = pos[i2];
std::set<std::pair<int, int> > st;
st.emplace(x1, y1);
for (auto [fx, fy] : dir) {
int x = x1 + fx, y = y1 + fy;
if (x >= 1 && x <= n && y >= 1 && y <= m)
st.emplace(x, y);
}
st.emplace(x2, y2);
for (auto [fx, fy] : dir) {
int x = x2 + fx, y = y2 + fy;
if (x >= 1 && x <= n && y >= 1 && y <= m)
st.emplace(x, y);
}
for (auto [x, y] : st)
work(x, y, -1);
std::swap(id[x1][y1], id[x2][y2]), std::swap(pos[i1], pos[i2]);
for (auto [x, y] : st)
work(x, y, 1);
return t[1].u;
}D - 单旋
https://www.luogu.com.cn/problem/P3721
- 发现任意时刻参与旋转的都是最值，简单分析可以发现做的这件事情是把最值移到根，其他点相对关系不变，转化为维护深度
- 考虑新加入点，可以利用 BST 的性质，直接查询 \(x\) 的前驱、后继，则二者存在祖孙关系，把 \(x\) 接在矮的下面即可
- 考虑做一个先删再加的过程，删会影响儿子的深度（显然只有一侧儿子），加会影响全树深度