CFR1098-D
Warning
警钟长鸣 ：：
set 容器读入后遍历做离散化复杂度 $> > $ sort(), unique()
题意
给你 $N$ 个格点 $(x_i, y_i)$，你可以划两个线，用一个二元组 $(k_1,k_2)$ 表示： $x = k_1 + 0.5, \ \ y = k_2 + 0.5$，这两条线会把平面内的所有点分在四个区域，四个区域的点会被染成固定的四种颜色，问共有多少中分割点的方式，当且仅当至少有一种点颜色的集合不同时，认为是不一样的分割方式.
约束
$\sum N \le 2 \cdot 10^6, \ \ \ 1 \le x_i, y_i \le N$
分析
不妨先考虑定一条竖着线的时候，横着的线可以怎么画：
玩一玩就会发现，设竖线左边的最大 $y$ 为 $Lmax$，左边最小为 $Lmin$，右边同理有 $Rmax, Rmin$. 会发现能划线的合法区域是 $(max(Lmin, Rmin), min(Lmax, Rmax))$ ，但是怎么样才能画出不同集合呢？
其实就是考虑在这个合法区间内有多少个 $y$ 值出现过，于是这样这道题就结束了.
书写代码
先记录每个 $x$ 的 $Xmax, Xmin$ （对应 $y$ 的最大最小）.
然后从左往右推一遍算 $Lmax, Lmin$，从右往左推一遍算 $Rmax, Rmin$.
别忘了直接扫一遍前缀和算出每一个 $y$ 有多少个 $y$ 出现过，这里是 $hasy$.
复杂度是 $O(N \cdot \log N)$，瓶颈在于离散化！
代码片段
该代码无法通过， TL；后者可以通过！
void Mainsol() {
INT(N);
v<I> Xmax(N + 1, -1), Xmin(N + 1, INF);
set<int> st;
v<I> po;
v<I> hasy(N + 2, 0);
rep(N) {
INT(x, y);
chmax(Xmax[x], y);
chmin(Xmin[x], y);
hasy[y + 1] = 1;
st.is(x);
}
rep(i, 1, sz(hasy)) hasy[i] += hasy[i - 1];
each(x, st) {
po.pb(x);
}
v<I> Lmax(N + 1, -1), Lmin(N + 1, INF), Rmax(N + 1, -1), Rmin(N + 1, INF);
I lsti = 0;
each(i, po) {
Lmax[i] = Xmax[i];
Lmin[i] = Xmin[i];
if(lsti) {
chmax(Lmax[i], Lmax[lsti]);
chmin(Lmin[i], Lmin[lsti]);
}
lsti = i;
}
auto poo = po;
rev(po);
lsti = 0;
each(i, po) {
Rmax[i] = Xmax[i];
Rmin[i] = Xmin[i];
if(lsti) {
chmax(Rmax[i], Rmax[lsti]);
chmin(Rmin[i], Rmin[lsti]);
}
lsti = i;
}
swap(po, poo);
ll ans = 0;
rep(j, sz(po) - 1) {
int i = po[j], ii = po[j + 1];
I hi = min(Lmax[i], Rmax[ii]);
I lo = max(Lmin[i], Rmin[ii]);
ll tt = hasy[hi] - hasy[lo];
dbg(j, i, ii, hi, lo, tt);
if(hi <= lo) continue;
ans += tt;
}
out(ans);
}void Mainsol() {
INT(N);
v<I> Xmax(N + 1, -1), Xmin(N + 1, INF);
v<I> po;
v<I> ppp;
v<I> hasy(N + 2, 0);
rep(N) {
INT(x, y);
chmax(Xmax[x], y);
chmin(Xmin[x], y);
hasy[y + 1] = 1;
po.push_back(x);
}
rep(i, 1, sz(hasy)) hasy[i] += hasy[i - 1];
uniq(po);
v<I> Lmax(N + 1, -1), Lmin(N + 1, INF), Rmax(N + 1, -1), Rmin(N + 1, INF);
I lsti = 0;
each(i, po) {
Lmax[i] = Xmax[i];
Lmin[i] = Xmin[i];
if(lsti) {
chmax(Lmax[i], Lmax[lsti]);
chmin(Lmin[i], Lmin[lsti]);
}
lsti = i;
}
auto poo = po;
rev(po);
lsti = 0;
each(i, po) {
Rmax[i] = Xmax[i];
Rmin[i] = Xmin[i];
if(lsti) {
chmax(Rmax[i], Rmax[lsti]);
chmin(Rmin[i], Rmin[lsti]);
}
lsti = i;
}
swap(po, poo);
ll ans = 0;
rep(j, sz(po) - 1) {
int i = po[j], ii = po[j + 1];
I hi = min(Lmax[i], Rmax[ii]);
I lo = max(Lmin[i], Rmin[ii]);
ll tt = hasy[hi] - hasy[lo];
dbg(j, i, ii, hi, lo, tt);
if(hi <= lo) continue;
ans += tt;
}
out(ans);
}