MX galaxy Day15

tree

交互。
首先，我们希望获得仅可能少的信息，因为多的我们根本无法处理。
进一步的，我们对于每个点，询问 \((u, 1)\) 累和。
想想我们得到了什么，除了根和叶子，所有点被算了三遍。
如果得知了根，叶子是好算的，想想如何得到根。
询问 \((u, h+1)\) ，找到深度为 \(1\) 和 \(2\) 的三个点，同时可以处理叶子的答案。
然后询问深度为 \(2\) 的点 \((u, 1)\) ，再减去 \((rt, 2)\) 。
可以做到 \(2n+4\) 。
发现确认深度 \(\le 2\) 的点不需要询问 \(n\) 次，询问 \(n-1\) 次即可确定。
做到 \(2n+3\) 次询问。

点击查看

#include <bits/stdc++.h>
#include "tree.h"
#define lep(i, a, b) for (int i = a; i <= b; ++i)typedef long long ll;
std::vector <int> E;long long solve(int subtask, int h) {if (subtask == 1) {bool flag = true; ll ans = 0;lep(i, 1, 3) {ll d = ask(i, 2);if (d) ans += d + (flag ? ask(i, 1) : 0), flag = false;}return ans;}int n = (1 << h) - 1; ll ans = 0, sum = 0;lep(i, 1, n - 1) {if (ask(i, h + 1)) ans += ask(i, 1);else E.push_back(i);}if (E.size() == 2) E.push_back(n);else ans += ask(n, 1);for (int i : E) { ll res = ask(i, 1), pos;ans += res;if (pos = ask(i, h)) {sum += res, ans += pos * 2;}else {sum -= ask(i, 2);}}E.clear();return (ans + sum / 2) / 3;
}

loong

首先考虑 \(a_i<b_i\) 的限制，发现一个合法的集合 \(S\) 一定满足 \(\forall\) \(i,j\in S\), \(a_i<b_j\) 。
所以我们一定能在值域上找到一个位置 \(t\) ，满足 \(a_{max}\le t\le b_{min}\) 。
对于每一个 \((a, b)\) , 看做一段闭区间，每次执行区间加一，全局询问单点最大值的操作。线段树即可。
我们称这样的区间为一类区间。

考虑 \(a_i>b_i\) 的情况，那么它能对某个 \(t\) 造成贡献当且仅当，\([b_i, a_i]\) 内的区间里都没有一类区间的端点。
因为这个区间是满足偏序的，所以只要落在区间里一个端点，就是不合法的。
我们称这样的区间为二类区间，可以发现二类区间最多选择一个。

如果一个二类区间包含了另一个，那么这个区间是没有用的。因为内部那个限制更小。
那么交叉的情况呢，发现只要对每个二类区间的右端点答案 \(+1\) 即可。
这样每个单点只会获得至多一个二类区间的贡献。

插入删除二类区间使用 \(set\) 维护，因为不存在包含关系，所以随着左端点递增，右端点也是递增的。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)const int _ = 2e6 + 7;
typedef long long ll;int n, mx[_ << 2], tag[_ << 2], c[_];
std::set<std::pair<int, int> > S;#define ls p << 1
#define rs p << 1 | 1
#define md ((s + t) >> 1)
void pu(int p) { mx[p] = std::max(mx[ls], mx[rs]); }
void upd(int p, int k) { mx[p] += k, tag[p] += k; }
void pd(int p) { if (tag[p]) upd(ls, tag[p]), upd(rs, tag[p]), tag[p] = 0; }
void mdy(int l, int r, int s, int t, int k, int p) {if (r < s or t < l) return;if (l <= s and t <= r) return upd(p, k); pd(p);mdy(l, r, s, md, k, ls), mdy(l, r, md + 1, t, k, rs); pu(p);
}
#undef ls
#undef rs
#undef md
void add(int x) { while (x <= 2 * n) ++c[x], x += x & -x; }
int qry(int x) { int res = 0; while (x) res += c[x], x -= x & -x; return res; }
void Del(int l, int r) {auto pos = S.lower_bound({-l, r});while (pos != S.end()) {auto nw = pos; ++pos;if (nw->second > r) mdy(nw->second, nw->second, 1, 2 * n, -1, 1), S.erase(nw);else break;}
}
void Mdy(int l, int r) { Del(l, l), Del(r, r), mdy(l, r, 1, 2 * n, 1, 1), add(l), add(r); }
bool ck(int l, int r) {auto pos = S.lower_bound({-l, r});if (pos != S.begin()) {--pos;if (pos->second < r) return true;}return false;
}
void Ins(int l, int r) {Del(l, r);if (qry(r) - qry(l - 1) > 0) return;if (ck(l, r)) return;mdy(r, r, 1, 2 * n, 1, 1), S.insert({-l, r});
}int main() {
#ifndef DEBUGfreopen("loong.in", "r", stdin);freopen("loong.out","w",stdout);
#endifscanf("%*d%d", & n); int a, b;lep(i, 1, n) {scanf("%d%d", & a, & b);if (a < b) Mdy(a, b);else Ins(b, a);printf("%d\n", mx[1]);}return 0;
}

lush