题目

L
题意大概是这样给一组序列,位置i,j可以连一条无向边当前仅当 i < j 且a[i] > a[j]
现在要你对这些点染色,染色规则是连边的相邻两点的颜色不同,输出方案中颜色最小值和方案

分析

先对样例进行分析

观察每次染色的规律:在染当前给的点的颜色时,我们是先找在这个点之前的所有比它点权大的点的
染色方式,比如1 3 4 2,记为a,b,c,d的点权
在当前点d的时候我们找的是点权为3,4的点b,c染色情况然后避开它的染色方式,那重点
就是如何快速找到b,c的染色情况,总不可能一个一个去找.那就得从前面比它点权大的点染色方式开
始着手,这就是本题最难的地方！(考场上没想出来 qwq),有一个规律就是说如果要染色就一定是前面所
有点权比它大的点的染色方式的最大值,首先解释一下这句话,以 1,3,4,2为例子,d前面的比它的点权大
的点是b,c,他们的染色方式是1,1所以当前点d应该染为2!!!这个如果可以参透就很好想了,我是这么想的:
每次判断染色方式就是要避免比它点权大的所有点,那这些点的染色方式是从1开始的,如果不是1,那在它们
的前面肯定早出现一个点权更大的值,而且这个的点也比当前点大!!!也得避免1啦.接着也会发现这些点
的染色方式一定是不重不漏的,也就是要染只能染染色方式最大值,假设中间漏了某个值,那么这个染色值必然
是出现过的,而且它的点权也必然比当前点大(一样的方式),因为漏的这个点的点权必然比这些点中的某个点的
点权大,也是得避免的!!(口胡)
于是我们从本来想一个一个找变成了只需要找要避免的染色方式的最大值就好了,这就是需要线段树了
线段树维护的信息:所有在树中的染色方式的最大值

#include<bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d",&x)
const int N =1e6+10;
int n;
int s[N],ans[N];
struct node
{
    int l,r;
    int v;
}tr[N*4];
void pushup(int u)
{
    tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);

}
void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x)  tr[u].v=v;

    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        if(x>mid)   modify(u<<1|1,x,v);
        else modify(u<<1,x,v);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)  return tr[u].v;
    else
    {
        int mid=tr[u].l+tr[u].r>>1;
        int res=0;
        if(l<=mid) res=query(u<<1,l,r);
        if(r>mid)   res=max(res,query(u<<1|1,l,r));
        return res;

    }
}
int main()
{
    int t;
    read(t);
    while(t--)
    {
        read(n);
        build(1,1,n);
        int res=0;
        for(int i=1;i<=n;i++)
        {
            read(s[i]);
            int t;
            if(s[i]<n)  t=query(1,s[i],n);//找到树中点权比s[i]大的染色方式的最大值
            else t=0;
            ans[i]=t+1;
            modify(1,s[i],ans[i]);//修改当前点权的染色方式
            res=max(res,ans[i]);
        }
        printf("%d\n",res);
        for(int i=1;i<=n;i++)   printf("%d ",ans[i]);
        puts("");
    }

    return 0;
}