反向按值建树 && 树状数组维护区间最大值

按值建树
反向建树
即大值在前，小值在后
这样方便求是否存在比x大的数，以及求比x大的数的最大颜色标号

树状数组维护的最大值是颜色标号的最大值

以后但凡看到，“ t组数据，每组n个数，且所有n之和不超过10^6 ” 之类的，都一律用for清空数组

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define low(x) x&(-x)
int const N=1e6+7;
int t,n,x,ans[N],maxn; //ans表示颜色标号
ll tr[N];
void add(ll w,int p){
    for(;p<=n;p+=low(p)){
        tr[p]=max(tr[p],w);
    }
}
ll ask(int p){
    ll res=0;
    for(;p>=1;p-=low(p)){
        res=max(res,tr[p]);
    }
    return res;
}

int main(){
    fio;
    cin >> t;
    while(t--){
        cin >> n;
        //memset(tr,0,sizeof tr);
        for(int i=1;i<=n;++i) tr[i]=0;
        maxn=0;
        for(int i=1;i<=n;++i){
            cin >> x;
            ans[i]=ask(n-x+1)+1;
            maxn=max(maxn,ans[i]);
            add(ans[i],n-x+1);
        }
        cout << maxn << "\n";
        for(int i=1;i<=n;++i){
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}