（dp）NOJ-2298

时间限制(普通/Java) : 4000 MS/ 12000 MS 运行内存限制 : 65536 KByte
总提交 : 91 测试通过 : 43
比赛描述

oo和他的同学因为破坏了太多虫洞违反了宇宙法被当局关了起来。牢狱中的生活十分无聊，他们决定探索一些奇怪的问题。他们找到了一些数列，oo学过严格递增子序列，但是他没学过最长递增子序列。现在他想知道在数列中的从每个位置开始（包含这一个位置）有多少种非递减子序列。

输入

输入：第一行一个整数T，表示case个数（1<=T<=1000)。对于每个case，第一行一个整数n。第二行n个数，表示整个数列。所有数用空格隔开（1<=n<=100)。

输出

每个case输出一行，n个数，用空格隔开，表示每个位置开始的非递减子序列的个数。

样例输入

1
6
1 2 3 1 2 3

样例输出

16 6 2 4 2 1

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<cassert>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>

using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxx=500050;
const ll INF = 2e18+4;
int n,m;
ll k;
int a[maxx];
int vis[maxx];
int ans = 0,cnt = 0,pos = 0;
int l = 0,r = 0;
ll A[maxx],dp[maxx];
set<int>s;
vector<int>que;
vector<int>v;
int getid(int x)
{
    return lower_bound(que.begin(),que.end(),x)-que.begin()+1;
}
void lisan(int a[],int n)
{
    for(int i=1; i<=n; i++)
    s.insert(a[i]);
    que.assign(s.begin(),s.end());
    for(int i=1; i<=n; i++)
    a[i]=getid(a[i]);
}
ll lowbit(ll x)
{
    return x & (-x);
}
void add(ll x,ll add)
{
    while(x <= n) { A[x]+=add; x+=lowbit(x); } } ll sum(ll x) { ll s=0; while(x > 0)
    {
        s += A[x];
        x -= lowbit(x);
    }
    return s;
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        s.clear();
        que.clear();
        memset(dp,0,sizeof(dp));
        memset(A,0,sizeof(A));
        scanf("%d",&n);
        rep(i,1,n+1){
            scanf("%d",&a[i]);
            a[i] = -a[i];
        }
        lisan(a,n);
        per(i,1,n+1){
            dp[i] = 1ll+sum(a[i]);
            add(a[i],dp[i]);
        }
        rep(i,1,n+1){
            if(i != n)printf("%lld ",dp[i]);
            else printf("%lld\n",dp[i]);
        }
    }
    return 0;
}