#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<vector>
#define max_int 2147483647
#define oo 1000000000
#define ll long long
#define db double
#define il inline
#define ms memset
#define mc memcpy
#define sz sizeof
#define gc getchar
#define fo freopen
il int maxx(int a,int b){return a>b?a:b;}
il int minn(int a,int b){return a<b?a:b;}
il void swap(int &a,int &b){int tt=a; a=b; b=tt; return;}
il void swap_ll(ll &a,ll &b){ll tt=a; a=b; b=tt; return;}
il void swap_db(db &a,db &b){db tt=a; a=b; b=tt; return;}
using namespace std;
#define maxn 110
struct treap_node
                {
                    int lc,rc,d,key,total;
                    #define lc(x) tr[x].lc
                    #define rc(x) tr[x].rc
                    #define d(x) tr[x].d
                    #define key(x) tr[x].key
                    #define total(x) tr[x].total
                }tr[maxn];
ll a[maxn],n,m,step[26],sum,root;
il void clear(int x)
{
    if (x!=-1) lc(x)=rc(x)=d(x)=key(x)=total(x)=0;
    return;  
}
il void updata(int x)
{
    clear(0);
    if (x!=-1) total(x)=total(lc(x))+total(rc(x))+1;
    return;   
}
il int l_rotate(int x)
{
    int y=rc(x),z=lc(rc(x));
    rc(x)=z; lc(y)=x;
    updata(x);
    return y;   
}
il int r_rotate(int x)
{
    int y=lc(x),z=rc(lc(x));
    lc(x)=z; rc(y)=x;
    updata(x);
    return y;   
}
il int ins(int w,int val)
{
    if (w==-1) w=++sum,lc(w)=rc(w)=-1,d(w)=val,total(w)=1,key(w)=rand();
    else
    {
        if (val<d(w))
        {
            lc(w)=ins(lc(w),val);
            if (key(lc(w))>key(w)) w=r_rotate(w);  
        }
        else
        {
            rc(w)=ins(rc(w),val);
            if (key(rc(w))>key(w)) w=l_rotate(w);    
        }
    }
    updata(w);
    return w;
}
il int del(int w,int val)
{
    if (val<d(w)) lc(w)=del(lc(w),val);
    else if (val>d(w)) rc(w)=del(rc(w),val);
    else
    {
        if (lc(w)==-1 && rc(w)==-1) w=-1;
        else if (lc(w)==-1) w=rc(w),clear(rc(w));
        else if (rc(w)==-1) w=lc(w),clear(lc(w));
        else
        {
            if (key(rc(w))>key(lc(w))) w=l_rotate(w),lc(w)=del(lc(w),val);
            else w=r_rotate(w),rc(w)=del(rc(w),val);
        }              
    }
    updata(w);
    return w;   
}
il int find(int w,int v)
{
    if (v<=total(lc(w))) return find(lc(w),v);
    else if (v==total(lc(w))+1) return d(w);
    else return find(rc(w),v-1-total(lc(w)));   
}
int main()
{
    int i,j,k,t;
    ll now;
    //fo("input.txt","r",stdin); fo("output.txt","w",stdout);
    srand(time(0));
    for (i=2,step[1]=1; i<=25; i++) step[i]=2*step[i-1];
    for (scanf("%d",&t); t; t--)
    {
        scanf("%I64d%I64d",&n,&m); m--;
        sum=total(0)=0; root=-1;
        for (i=1; i<=n; i++) root=ins(root,i);
        while (n>1)
        {
            n--,now=m/step[n],m%=step[n];
            now=find(root,now+1); root=del(root,now);
            printf("%d ",now);  
        }
        printf("%d\n",d(root));
    }
    return 0;
}

• 求大牛显灵现身，求解释，理论空间复杂度绝对不会爆的啊！！！！ (0) shuaige123 2012-11-07 16:25:43
• 精诚所至金石为开，发帖向路过的大牛们求救! T-T (0) shuaige123 2012-11-08 08:05:50
• 类似康托展开的方法。 (3409) yygy 2014-06-23 15:06:09