题目
题解
对于每个询问，我们让修改次数较小的人来计算。
按顺序处理每次操作，维护当前每个人是否在线，以及到目前为止的总在线时间，差分计算答案。
需要记忆化。我们分析时间复杂度：
$$\sum\limits_{1 \leq i \leq \sqrt n}O\left(i \operatorname{op}_i\right) \leq \sum\limits_{1 \leq i \leq \sqrt n}O\left(n\right) = O\left(n \sqrt n\right)$$
还有一个逆天做法，对于每个询问暴力，记忆化。
这个其实不好卡，最好的方法是让 $5\times 10^4$ 个修改 $10^5$ 的人互相询问。但这样也只有 $2.5\times10^9$，常数太小，可以通过。
代码
/* C++17 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* I've reached the end of my fantasy.
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
#define LOAD5($1, $2, $3, $4, $5, ...) $5
#define __GOR1(b) for (tp _COUNTER_ = 0; _COUNTER_ < tp(b); ++_COUNTER_)
#define __DOR1(b) for (tp _COUNTER_ = 1; _COUNTER_ <= tp(b); ++_COUNTER_)
#define __GOR2(i, b) for (tp i = 0; i < tp(b); ++i)
#define __DOR2(i, b) for (tp i = 1; i <= tp(b); ++i)
#define __GOR3(i, a, b) for (tp i = tp(a); i < tp(b); ++i)
#define __DOR3(i, a, b) for (tp i = tp(a); i <= tp(b); ++i)
#define __GOR4(i, a, b, c) for (tp i = tp(a); i < tp(b); i += tp(c))
#define __DOR4(i, a, b, c) for (tp i = tp(a); i <= tp(b); i += tp(c))
#define dor(...) LOAD5(__VA_ARGS__, __GOR4, __GOR3, __GOR2, __GOR1)(__VA_ARGS__)
#define gor(...) LOAD5(__VA_ARGS__, __DOR4, __DOR3, __DOR2, __DOR1)(__VA_ARGS__)
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
tp n, m; bin >> n >> m;
vector t = bin.vcr<pair<tp, tp>>(m);
vetp cnt(n + 1, 0);
for (auto& [$, i] : t) ++cnt[i];
vetp ps(n + 1, 0);
vetp lst(n + 1, 0);
tp q = bin;
map<pair<tp, tp>, tp> pid;
vetp tid(q, 0);
vector<vector<pair<tp, tp>>> upd(n + 1);
gor(i, q) {
tp a, b; bin >> a >> b;
if (cnt[a] > cnt[b]) swap(a, b);
if (tp t = pid.size(); !pid.count(make_pair(a, b))) {
pid[make_pair(a, b)] = t;
upd[a].emplace_back(b, t);
}
tid[i] = pid[make_pair(a, b)];
}
vetp tar(pid.size(), 0);
vetp online(n + 1, 0);
auto ntime = [&](tp x, tp t) -> auto { return ps[x] + online[x] * (t - lst[x]); };
for (auto& [t, x] : t) {
for (auto& [j, k] : upd[x]) {
tar[k] += (online[x] ? 1 : -1) * ntime(j, t);
}
if (online[x]) ps[x] += t - lst[x];
else lst[x] = t;
online[x] ^= 1;
}
gor(i, q) bin << tar[tid[i]] << '\n';
return 0;
}
void MIST() {
}
// :\ */