2021ICPC昆明 L.Simone and graph coloring

题目链接
题目描述
Simone, a student of Graph Coloring University, is interested in permutation. Now she is given a permutation of length $n$ , and she finds that if she connects each inverse pair, she will get a graph. Formally, for the given permutation, if $i<j$ and $a_i>a_j$ , then there will be an undirected edge between node $i$ and node $j$ in the graph.

Then she wants to color this graph. Please achieve poor Simone’s dream. To simplify the problem, you just need to find a way of coloring the vertices of the graph such that no two adjacent vertices are of the same color and minimize the number of colors used.

输入描述:
There are multiple test cases. The first line of the input contains an integer $T(1\le T\le 10^6)$ , indicating the number of test cases.

For each test case, the first line contains an integer $n(1\le n\le 10^6)$ , indicating the length of the permutation.

The second line contains nn integers $a_1,a_2,...,a_n$ , indicating the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ .
输出描述:
For each test case, the first line contains an integer $c$ , the chromatic number(the minimal number of colors been used when coloring) of the graph.

The second line contains nn integers $c_1,c_2,...,c_n$ , the color of each node.

Notice that $c_i$ should satisfy the limit that $1\le c_i\le c$ .

If there are several answers, it is acceptable to print any of them.
示例1
输入

2
4
1 3 4 2
2
1 2

输出

2
1 1 1 2 
1
1 1

简单题愣是卡了2h才过
比赛的时候很快就推出了需要的颜色数是该序列不断取 LIS 最终能取到的数量，即不同的 LIS 染不同的颜色，然后推出这个数量等于最长下降子序列的长度。但是在输出方案上想偏了。
一开始想暴力维护复杂度为 $O(n^2\log n)$ ，考虑从前往后扫，从哪个点转移过来就和那个点染一样的颜色这样复杂度就可以降为 $O(n\log n)$ ，然后上去就敲了一个树状数组，写完之后发现样例过不去。分析发现，不同 LIS 会出现重合的情况，然后想用完一个元素就标记为 $-\inf$ 删掉，发现树状数组在维护前缀最小值时无法进行删除操作，遂改线段树。期间队友提供了一个动态维护后缀 MEX 的策略，想到之前写过一个主席树动态查询区间 MEX 操作，但是这个显然不支持修改操作，再后来发现我的线段树的做法也假了，因为 dp 的中间状态不一定是最终状态，即 LIS 不一定就是这么转移的。看一眼榜发现这个题被过穿了，不应该这么难，估计是想麻烦了。后来就发现只需要贪心的维护若干个以最长下降子序列的为结尾上升子序列即可满足条件，这才过掉此题。
这道题卡题主要还是思路上想偏了，前面的最少颜色数是按不断找 LIS 的策略得出的，于是在构造方案时一直往找 LIS 的方向想。实际上只要能把序列划分为若干个上升子序列，每个子序列个染一种颜色就可以做到所有逆序对颜色不同，而划分的上升子序列的数量等于最长下降子序列的长度，因而在构造方案时不用考虑不断找 LIS 的操作。这说明在比赛时缺乏观察性质和思维转换能力，在简单题上耽误时间。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int n, T, a[N], b[N], id[N], ans[N], tot;

int main() {
   
    scanf("%d", &T);
    while (T--) {
   
        scanf("%d", &n), tot = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), id[a[i]] = i;
        for (int i = n, p; i >= 1; i--) {
   
            if (!tot || a[i] > b[tot])b[++tot] = a[i], ans[i] = tot;
            else {
   
                p = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
                ans[i] = ans[id[b[p]]], b[p] = a[i];
            }
        }
        printf("%d\n", tot);
        for (int i = 1; i <= n; i++)
            printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}