typedef unsigned int u32;
u32 b[200000000],cnt0[256],cnt8[256],cnt16[256],cnt24[256];
void sort(u32 *a,int n)
{
for(int i=0;i<n;++i){
++cnt0[a[i]&255];
++cnt8[a[i]>>8&255];
++cnt16[a[i]>>16&255];
++cnt24[a[i]>>24&255];
}
for(int i=1;i<=255;++i){
cnt0[i]+=cnt0[i-1];
cnt8[i]+=cnt8[i-1];
cnt16[i]+=cnt16[i-1];
cnt24[i]+=cnt24[i-1];
}
int tim=n>>3;//循环展开为8
u32 *now=a+n-1,*bb=b,*cnt=cnt0;
while(tim--){
bb[--cnt[now[0]&255]]=now[0];
bb[--cnt[now[-1]&255]]=now[-1];
bb[--cnt[now[-2]&255]]=now[-2];
bb[--cnt[now[-3]&255]]=now[-3];
bb[--cnt[now[-4]&255]]=now[-4];
bb[--cnt[now[-5]&255]]=now[-5];
bb[--cnt[now[-6]&255]]=now[-6];
bb[--cnt[now[-7]&255]]=now[-7];
now-=8;
}
now-=(n&7);
switch(n&7){
case 7:bb[--cnt[now[1]&255]]=now[1];
case 6:bb[--cnt[now[2]&255]]=now[2];
case 5:bb[--cnt[now[3]&255]]=now[3];
case 4:bb[--cnt[now[4]&255]]=now[4];
case 3:bb[--cnt[now[5]&255]]=now[5];
case 2:bb[--cnt[now[6]&255]]=now[6];
case 1:bb[--cnt[now[7]&255]]=now[7];
}
tim=n>>3;//循环展开为8
now=b+n-1,bb=a,cnt=cnt8;
while(tim--){
bb[--cnt[now[0]&255]]=now[0];
bb[--cnt[now[-1]&255]]=now[-1];
bb[--cnt[now[-2]&255]]=now[-2];
bb[--cnt[now[-3]&255]]=now[-3];
bb[--cnt[now[-4]&255]]=now[-4];
bb[--cnt[now[-5]&255]]=now[-5];
bb[--cnt[now[-6]&255]]=now[-6];
bb[--cnt[now[-7]&255]]=now[-7];
now-=8;
}
now-=(n&7);
switch(n&7){
case 7:bb[--cnt[now[1]&255]]=now[1];
case 6:bb[--cnt[now[2]&255]]=now[2];
case 5:bb[--cnt[now[3]&255]]=now[3];
case 4:bb[--cnt[now[4]&255]]=now[4];
case 3:bb[--cnt[now[5]&255]]=now[5];
case 2:bb[--cnt[now[6]&255]]=now[6];
case 1:bb[--cnt[now[7]&255]]=now[7];
}
tim=n>>3;//循环展开为8
now=a+n-1,bb=b,cnt=cnt16;
while(tim--){
bb[--cnt[now[0]&255]]=now[0];
bb[--cnt[now[-1]&255]]=now[-1];
bb[--cnt[now[-2]&255]]=now[-2];
bb[--cnt[now[-3]&255]]=now[-3];
bb[--cnt[now[-4]&255]]=now[-4];
bb[--cnt[now[-5]&255]]=now[-5];
bb[--cnt[now[-6]&255]]=now[-6];
bb[--cnt[now[-7]&255]]=now[-7];
now-=8;
}
now-=(n&7);
switch(n&7){
case 7:bb[--cnt[now[1]&255]]=now[1];
case 6:bb[--cnt[now[2]&255]]=now[2];
case 5:bb[--cnt[now[3]&255]]=now[3];
case 4:bb[--cnt[now[4]&255]]=now[4];
case 3:bb[--cnt[now[5]&255]]=now[5];
case 2:bb[--cnt[now[6]&255]]=now[6];
case 1:bb[--cnt[now[7]&255]]=now[7];
}
tim=n>>3;//循环展开为8
now=b+n-1,bb=a,cnt=cnt24;
while(tim--){
bb[--cnt[now[0]&255]]=now[0];
bb[--cnt[now[-1]&255]]=now[-1];
bb[--cnt[now[-2]&255]]=now[-2];
bb[--cnt[now[-3]&255]]=now[-3];
bb[--cnt[now[-4]&255]]=now[-4];
bb[--cnt[now[-5]&255]]=now[-5];
bb[--cnt[now[-6]&255]]=now[-6];
bb[--cnt[now[-7]&255]]=now[-7];
now-=8;
}
now-=(n&7);
switch(n&7){
case 7:bb[--cnt[now[1]&255]]=now[1];
case 6:bb[--cnt[now[2]&255]]=now[2];
case 5:bb[--cnt[now[3]&255]]=now[3];
case 4:bb[--cnt[now[4]&255]]=now[4];
case 3:bb[--cnt[now[5]&255]]=now[5];
case 2:bb[--cnt[now[6]&255]]=now[6];
case 1:bb[--cnt[now[7]&255]]=now[7];
}
}