今天下午又打多校赛了，这次水有点浑，一条鱼也没摸到。

其实，只差一个改longlong就能ac的，主要是我们组违规操作，三个人各自打代码（因为一开始想到是线段树的题目但没有完整思路），后来我 试图去理解队友的代码，但发现太难理解，就效率比较低，最后痛失一题。

不过，考完试我发现一个小优化的地方：
权值线段树要离散化，但是不要去重。这样就可以不用考虑一个值有多个数字还要判断有几个？取几个？的问题。

权值线段树模板/hdu6609AC代码

前两次WA是多行输出结果了，应该是用空格隔开。

//#define LOCAL

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 200100
#define nowp SegT[id]
#define lson SegT[id].lef_id
#define rson SegT[id].rig_id
#define ll long long
using namespace std;

struct NumId{
    int num;
    int id;
    bool operator < (NumId o){return num<o.num;}
};
int M, N;
NumId a[MAXN];
int ranks[MAXN];//Ranking/discretized(离散化的) values for each number
int query[MAXN];//Record each query, because they may be the same value
/*
 * The input of this question is a little strange.
 * query[i] means that after you add the query[i](th) number, query the ith bigger number in the box.
*/
struct SegTree{
    int lef_id;
    int rig_id;
    int  val;
    ll   sum;
};
SegTree SegT[MAXN*4];
int segRoot;
int seg_num;
void build(int &id, int SegL, int SegR)
{
    id = ++seg_num;
    nowp.val = 0;
    nowp.sum = 0;
    if(SegL == SegR)
        return ;
    int SegMid = (SegL+SegR)/2;
    build(lson, SegL, SegMid);
    build(rson, SegMid+1, SegR);
}

void add_num(int id, int num, int SegL, int SegR)
{
    if(SegL == SegR)
    {
        nowp.val++;
        nowp.sum += a[num].num;
        return ;
    }
    int SegMid = (SegL+SegR)/2;
    if(num <= SegMid)
        add_num(lson, num, SegL, SegMid);
    else
        add_num(rson, num, SegMid+1, SegR);
    nowp.val++;
    nowp.sum += a[num].num;
    //nowp.val = SegT[lson].val + SegT[rson].val;//push up
}

int get_Nth_num(int id, ll rest, int SegL, int SegR)
{
    if(nowp.sum <= rest)
        return nowp.val;
    if(SegL == SegR)
    {
        return nowp.sum<=rest;//error01 return SegL
    }
    int SegMid = (SegL+SegR)/2;
    if(SegT[lson].sum >= rest)
        return get_Nth_num(lson, rest, SegL, SegMid);
    else
        return SegT[lson].val+get_Nth_num(rson, rest-SegT[lson].sum, SegMid+1, SegR);
}

int main()
{
#ifdef LOCAL
    freopen("1.in", "r", stdin);
    freopen("1.ou", "w", stdout);
#endif
    int caseN;
    scanf("%d", &caseN);
    while(caseN--)
    {
        scanf("%d%d", &N, &M);
        for(int i = 1; i < N+1; i++)
        {
            scanf("%d", &a[i].num);
            a[i].id = i;
        }
        sort(a+1, a+N+1);
        for(int i = 1; i < N+1; i++)//It's silly for a weight line segment tree/权值线段树 to delete duplicate/相同 elements.
        {
            ranks[a[i].id] = i;//The discretization/离散化 value of element with original subscript/index a[i].id is i
        }
        //Read-in data and discretization/离散化 has been done!

        seg_num = 0;
        build(segRoot, 1, N);
        int cnt = 1;//Record index of query array for current traversal
        for(int i = 1; i < N+1; i++)
        {
            printf("%d ", i-1-get_Nth_num(segRoot, M-a[ranks[i]].num, 1, N));//error2 M-ranks[i]
            add_num(segRoot, ranks[i], 1, N);
        }
        printf("\n");
    }
    return 0;
}