题解：P17600 「RiOI-8」城ケ崎 ノア

· · 题解

题解区怎么没有我的做法，感觉二分+序列并查集比较自然。

保证整体思路和代码全部由人类完成，但是由于笔者表达能力太菜某些部分使用 gpt 辅助解释证明。

思路

有个比较显然的贪心：想要丑陋度最小，如果一个区间后面还能再放一个区间，放 l_i 最小的一个区间一定最优。一行有多个区间一定不与别的有区间的行相邻。并对于剩余的散区间，在剩余可放的行中，能不相邻即不相邻（能空行就空行）。

::::info[gpt 给的贪心策略的严谨化版本] 存在一个最优方案，使多区间的行都不与其他非空行相邻；其余单区间行尽量用空行隔开。 ::::

::::info[我给出一个比较感性的证明。]

如果合并了一个区间，那么可以天然地空出一行，受到合并的区间一定可以不再受到干扰。

要放 l_i 最小的区间，显然如果放 l_i 更大的区间，当前这个区间更难被更新到，可能有读者会认为放 r_i 较小的可能优，但是我们其实是对于每个区间独立考虑，r_i 较小的区间的优势在于它的后面还能再跟区间，这样显然它也会不受干扰，所以一定不劣。

那么我们很容易知道，最后没有被合并的区间一定能互相有交，不论如何排列都无法避免有丑陋度，如果想要避免这些区间获得丑陋度，此时除了最后一句的避免方法，剩下想要避免必定会干扰到上面的多区间的行，这样一定不优。

::::info[gpt 给的证明。]

设第 i 个区间为 I_i=[l_i,r_i]，并令

K=\max_x\left|\{i:l_i\le x\le r_i\}\right|,

即同一列中最多有多少个区间覆盖它。画布共有 n 行，因此 1\le t_i\le n。

下面证明最小丑陋度为

\boxed{\max(0,\,2K-n-1)}.

一、丑陋度的下界

取一列 x，使得恰有 K 个区间覆盖它，并将这些区间记为集合 C。

集合 C 中的区间两两在第 x 列重叠，因此：

设这 K 个区间所在的行分成 c 段连续的行。例如，占用行号为 1,2,4,6,7 时，分成 3 段。

每一段中，若有 d 个区间，就有 d-1 对相邻行。因此，集合 C 中的区间至少贡献

K-c

点丑陋度。

相邻两段之间至少要有一个不属于 C 的行。总共只有 n-K 个这样的行，所以

c\le n-K+1.

于是

\text{丑陋度}\ge K-c\ge K-(n-K+1)=2K-n-1.

又因为丑陋度非负，所以

\text{丑陋度}\ge \max(0,\,2K-n-1).

二、构造达到下界的方案

1. 将区间分成 K 组

按 l_i 从小到大处理区间。维护若干组，每组内的区间按处理顺序排列。

处理区间 [l_i,r_i] 时：

这里要求右端点严格小于 l_i，因为区间端点相同也表示它们覆盖同一列。

这样每组中的区间互不重叠，可以放在同一行。这个贪心恰好得到 K 组：

因此总共正好有 K 组。

由于集合 C 中的 K 个区间两两重叠，它们必须位于不同组中；而总共只有 K 组，所以每组恰好包含一个 C 中的区间。

2. 安排各组对应的行

设：

每个多区间组都包含一个 C 中的区间，并至少多包含一个其他区间。因此

a\le e.

先拿出 a 个空行，把每个多区间组和一个空行相邻放置。这样所有多区间组都不会与其他有区间的行相邻。

还剩

q=e-a

个空行，以及 b 个单区间组。把这 q 个空行尽量插在单区间组之间，可以把它们分成至多 q+1 段。因此，相邻的单区间组对数最少为

\max(0,\,b-q-1).

每个单区间组中的区间都属于 C，所以任意两个相邻的单区间组会在列 x 重叠，恰好贡献一次晕染。多区间组都被空行隔开，不会产生额外晕染。于是总丑陋度为

\begin{aligned} \max(0,\,b-q-1) &=\max(0,\,(K-a)-(e-a)-1)\\ &=\max(0,\,K-e-1)\\ &=\max(0,\,2K-n-1). \end{aligned}
这与下界相等，因此构造最优。

实现是简单的。记一下原下标，按照 l_i 排序，如果当前区间后面还能接区间，就让被合起来的区间的行数等于当前区间所在行数。找最小的 l_i 用二分+序列并查集即可维护，二分找到最小的，序列并查集找到最小没有选的。

构造按照上面的贪心策略把原来我们构造出的区间所在行重构并且按照原下标还原出来即可。

代码

::::success[code]

#include <bits/stdc++.h>
char buf[1000010], obuf[1000010], *p1, *p2, *p3=obuf;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1000000, stdin), p1==p2) ? EOF : *p1++)
#define pc(x) (p3==obuf+1000000&&fwrite(p3=obuf, 1, 1000000, stdout), *p3++=(x))
#define LF pc('\n')
#define SP pc(' ')
#define ll unsigned long long
#define ui unsigned int
#define N 1000005
#define M 1000005
#define K 20
#define INF 0x3f3f3f3f
#define tT template<typename T>
#define tA template<typename T, typename... Ts>
using namespace std;
namespace FastIO {
    tT inline void read(T& x) {
        x=0; char ch=gc; while(ch<'0'||ch>'9') ch=gc;
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch&15), ch=gc;
    }
    tA inline void read(T& x, Ts&... args) { read(x); read(args...); }
    tT inline void write(T x) {
        if(x==0) { pc('0'); return ; }
        static ui a[40]; ui t=0; while(x) a[++t]=x%10, x/=10; while(t) pc(a[t--]|48);
    }
    tA inline void write(T x, Ts... args) { write(x); if(sizeof...(args)!=0) { SP; write(args...); } }
}
using namespace FastIO;
namespace M_K_W_ {
    tT inline T max(const T a, const T b) { return a>b ? a : b; }
    tT inline T min(const T a, const T b) { return a<b ? a : b; }
    struct node { ui l, r, i; } a[N];
    ui n, f[N], g[N], cnt[N], now[N], ans, b[N];
    inline bool cmp(node a, node b) {
        return a.l==b.l ? a.i<b.i : a.l<b.l;
    }
    inline ui Find(const ui x) {
        return x==f[x] ? x : f[x]=Find(f[x]);
    }
    inline ui bound(ui l, ui r, const ui x) {
        while(l<=r) {
            const ui mid=l+r>>1;
            if(a[mid].l>x) r=mid-1;
            else l=mid+1; 
        } return Find(l);
    }
    inline void solve() {
        read(n); ans=n-1;
        for(ui i=1; i<=n; ++i)
            read(a[i].l, a[i].r), cnt[a[i].i=f[i]=g[i]=i]=now[i]=0;
        f[n+1]=n+1;
        sort(a+1, a+1+n, cmp);
        for(ui i=1; i<n; ++i) {
            const ui t=bound(i+1, n, a[i].r);
            if(t<=n)
                f[t]=Find(t+1), ++cnt[g[t]=g[i]], ans-=2;
        } ui p=1, x=0;
        if(ans<n) write(ans), LF;
        else pc('0'), LF;
        for(ui i=1; i<=n; ++i)
            if(g[i]==i&&cnt[g[i]]>0)
                now[i]=p, p+=2, x+=cnt[g[i]]-1;
        for(ui i=1; x&&i<=n; ++i)
            if(x&&g[i]==i&&!cnt[g[i]])
                now[i]=p, p+=2, --x;
        for(ui i=1; i<=n; ++i)
            if(g[i]==i&&!now[i])
                now[i]=p++;
        for(ui i=1; i<=n; ++i)
            b[a[i].i]=now[g[i]];
        for(ui i=1; i<n; ++i)
            write(b[i]), SP;
        write(b[n]), LF;
    }
    inline void main() {
        ui T;
        read(T);
        while(T--)
            solve();
    }
}
int main() {
    M_K_W_ :: main();
    fwrite(obuf, 1, p3-obuf, stdout);
    return 0;
}

::::