题面
JOI 社为了扩大业务而开始了新社员招募。社员有 \(N\) 名候补者，编号从 \(1\) 到 \(N\)，每名候补者有称为评价值的一个确定整数。评价值高于某一个值的候补者全部都将被聘用，他们还将分为几个组别。如果 \(a, b(a \lt b)\) 同时被聘用且 \(c(a \le c\le b)\) 全部被聘用时，\(a,b\) 进入同一组。
你要处理 \(M\) 个查询，查询有以下两种：
-
评价值 \(B_j\) 以上的候补者全部聘用时的组数；
-
将候补者 \(C_j\) 的评价值更新为 \(D_j\)。
题解
本题存在根号复杂度做法。
思考过程相对朴素，考虑将询问转化为一个二元组 \(\left(time, x\right)\) 表示在第 \(time\) 个修改操作后询问评价值 \(x\) 的组数。
考虑莫队，以 \(time\) 所在块编号为第一关键字，\(x\) 的大小为第二关键字进行排序。答案的处理则可以维护一个 \(\text{bitset}\)，每次修改时判断两侧点的状态来决定对答案贡献的影响。
注意一点，排序只能按上文所说的方法进行排序，因为单次修改的复杂度为严格的 \(\mathcal{O}(1)\)，而 \(x\) 这一边界移动的复杂度为均摊 \(\mathcal{O}(1)\)，如果颠倒排序顺序则无法保证复杂度。关于\(x\) 这一边界移动的复杂度为均摊 \(\mathcal{O}(1)\) 的证明可以考虑将 \(x\) 从最小值移动到最大值每个候补者状态至多更新一次。
该种做法如果想在 \(\text{LOJ}\) 上通过（应该）需要精湛的卡常技巧。笔者秉持着人傻常数大的人生理念成功被卡常。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::set<valueType> ValueSet;
typedef std::vector<ValueSet> SetVector;
typedef std::vector<bool> bitset;
constexpr valueType MAXN = 2e5 + 5;
class Recorder {
private:
valueType N, ans;
bitset data;
public:
explicit Recorder(valueType n) : N(n), ans(0), data(n + 1, false) {}
void set(valueType i) {
data[i] = true;
if (i > 1 && data[i - 1] && i < N && data[i + 1])
--ans;
else if ((i == 1 || !data[i - 1]) && (i == N || !data[i + 1]))
++ans;
}
void reset(valueType i) {
data[i] = false;
if (i > 1 && data[i - 1] && i < N && data[i + 1])
++ans;
else if ((i == 1 || !data[i - 1]) && (i == N || !data[i + 1]))
--ans;
}
valueType get() const {
return ans;
}
void set(ValueSet const &pos) {
for (auto const &iter: pos)
set(iter);
}
void reset(ValueSet const &pos) {
for (auto const &iter: pos)
reset(iter);
}
};
std::array<valueType, MAXN> belong;
struct Modify {
valueType pos, pre, to;
Modify() = default;
Modify(valueType p, valueType pre, valueType to) : pos(p), pre(pre), to(to) {}
};
struct Query {
valueType time, key, id;
Query() = default;
Query(valueType t, valueType k, valueType i) : time(t), key(k), id(i) {}
bool operator<(Query const &other) const {
if (belong[time] != belong[other.time])
return belong[time] > belong[other.time];
if (belong[time] & 1)
return key > other.key;
else
return key < other.key;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M;
std::cin >> N >> M;
valueType const Block = std::ceil(std::pow(M, 0.5));
for (valueType i = 1; i <= M; ++i)
belong[i] = (i - 1) / Block + 1;
ValueVector source(N + 1), bucket({0, INT_MIN, INT_MAX});
bucket.reserve(N + M + 3);
for (valueType i = 1; i <= N; ++i) {
std::cin >> source[i];
bucket.push_back(source[i]);
}
std::vector<Modify> modify(1, Modify(0, INT_MIN, INT_MIN));
std::vector<Query> query;
modify.reserve(M);
query.reserve(M);
for (valueType i = 1; i <= M; ++i) {
int type;
std::cin >> type;
if (type == 1) {
valueType x;
std::cin >> x;
query.emplace_back(modify.size() - 1, x, query.size());
bucket.push_back(x);
} else {
valueType x, y;
std::cin >> x >> y;
modify.emplace_back(x, y, source[x]);
source[x] = y;
bucket.push_back(y);
}
}
std::sort(bucket.begin(), bucket.end());
bucket.erase(std::unique(bucket.begin(), bucket.end()), bucket.end());
auto const S = (valueType) bucket.size() - 1;
SetVector pos(S + 1);
for (valueType i = 1; i <= N; ++i) {
source[i] = (valueType) std::distance(bucket.begin(),
std::lower_bound(bucket.begin(), bucket.end(), source[i]));
pos[source[i]].insert(i);
}
for (auto &iter: modify) {
iter.pre = (valueType) std::distance(bucket.begin(),
std::lower_bound(bucket.begin(), bucket.end(), iter.pre));
iter.to = (valueType) std::distance(bucket.begin(),
std::lower_bound(bucket.begin(), bucket.end(), iter.to));
}
for (auto &iter: query)
iter.key = (valueType) std::distance(bucket.begin(),
std::lower_bound(bucket.begin(), bucket.end(), iter.key));
Recorder recorder(N);
std::sort(query.begin(), query.end());
ValueVector ans(query.size());
valueType nowTime = (valueType) modify.size() - 1, nowKey = S;
for (auto const &iter: query) {
while (nowKey > iter.key) {
--nowKey;
recorder.set(pos[nowKey]);
}
while (nowKey < iter.key) {
recorder.reset(pos[nowKey]);
++nowKey;
}
while (nowTime < iter.time) {
++nowTime;
Modify &mod = modify[nowTime];
pos[mod.pre].erase(mod.pos);
pos[mod.to].insert(mod.pos);
if (mod.pre >= nowKey && mod.to < nowKey)
recorder.reset(mod.pos);
else if (mod.to >= nowKey && mod.pre < nowKey)
recorder.set(mod.pos);
// source[mod.pos] = mod.to;
std::swap(mod.pre, mod.to);
}
while (nowTime > iter.time) {
Modify &mod = modify[nowTime];
pos[mod.pre].erase(mod.pos);
pos[mod.to].insert(mod.pos);
if (mod.pre >= nowKey && mod.to < nowKey)
recorder.reset(mod.pos);
else if (mod.to >= nowKey && mod.pre < nowKey)
recorder.set(mod.pos);
// source[mod.pos] = mod.to;
std::swap(mod.pre, mod.to);
--nowTime;
}
ans[iter.id] = recorder.get();
}
for (auto const &iter: ans)
std::cout << iter << '\n';
std::cout << std::flush;
return 0;
}