1.康托展開是個啥一句話，給出一個全排列，求它是第幾個全排列，叫做康托展開。 另一句話，給出全排列長度和它是第幾個全排列，求這個全排列，叫做逆康托展開。 這里，全排列的順序定義和火星人中的定義是一樣的。 2.暴力康托展開對于一個全排列，第i為有n+1-i種選擇，如果用變進制數(shù)表示，這一位就是n+1-i進制的。如果這一位選擇了第k種情況，那么對應(yīng)的變進制數(shù)的這一位就是k。 為了方便起見，通常以0起下標。 舉個栗子：
例1.12345變成變進制數(shù)是(00000) 首位1是5種選擇{1,2,3,4,5}的第1種，故變?yōu)? 次位2是4種選擇{2,3,4,5}的第1種，故變?yōu)? 【解釋：為什么是4種選擇，其實是還沒有使用過的數(shù)字的總數(shù)，下同】 中間位3是3種選擇{3,4,5}的第1種，故變?yōu)? 次低位4是2種選擇{4,5}的第1種，故變?yōu)? 末位5是1種選擇的{5}第1種，故變?yōu)?
最后，1,2,3,4,5變成了(00000)_{unknown} 例2.把1,4,5,2,3變成變進制數(shù) 首位1是5種選擇{1,2,3,4,5}的第1種，故變?yōu)? 次位4是4種選擇{2,3,4,5}的第3種，故變?yōu)? 中間位5是3種選擇{2,3,5}的第3種，故變?yōu)? 次低位2是2種選擇{2,3}的第1種，故變?yōu)? 末位3是1種選擇的{3}第1種，故變?yōu)?
最后，1,4,5,2,3變成了(02200)_{unknown} 我們看到，第i位的值就是a_i減去它左邊比它小的數(shù)的數(shù)量-1 //n表示全排列長度
for(int i=1;i<=n;i++)
{
cin>>a[i];
int x=a[i];
for(int j=1;j<=a[i];j++)
x-=used[j];
//used[j]表示j是否用過(1用過，0沒用）
used[a[i]]=1;
a[i]=x-1;
}
有了變進制形式的結(jié)果，把它轉(zhuǎn)換成10進制就可以了。 long long res=0;
for(int i=1;i<n;i++)
res=(res+a[i])*(n-i);
3.線段樹康托展開我們看到，剛才的方法有兩重循環(huán)，時間復雜度為O(N^2),找左側(cè)用過的數(shù)的數(shù)量很費時間。 只要把used函數(shù)用線段樹維護區(qū)間和，就可以只花log的時間就求出左側(cè)小于自己的數(shù)的個數(shù)了。 //從這兒開始，tt是長度，n是線段樹大小
for(int i=1;i<=tt;i++)
{
scanf('%d',&a[i]);
upd(a[i]+n);
//upd更新一個節(jié)點
a[i]-=sum(1,a[i],1,n,1)+1;
//sum(x,y,l,r,root)=x到y(tǒng)的區(qū)間和，在l到r區(qū)間找，根節(jié)點在root
}
這里所有數(shù)字都是單點修改，所以我沒寫懶標記。 線段樹這種東西，你們的碼風應(yīng)該比我好，常數(shù)也應(yīng)該比我小，就不展示了。 你都看到這兒了，還不去試一試? 4.線段樹逆康托展開接下來，我們先把給出的數(shù)據(jù)轉(zhuǎn)成變進制形式。線段樹都寫的出來的人，這種小事應(yīng)該不用講吧。 我們要完成的工作就是，對于每個數(shù)位a[i]，求出x使得x前面的數(shù)中恰好有a[i]個0。
這里我們可以用二分，每次查詢左子樹上0的數(shù)量，如果不夠，答案就在右子樹，否則在左子樹上繼續(xù)找。 int fx(int l,int r,int x,int root)
//在l到r范圍找出有x個0的位置
{
if(l==r)
return l;
int mid=(l+r)>>1,sss=sum(l,mid,l,r,root);
if(mid-l+1-sss>x)
return fx(l,mid,x,root<<1);
return fx(mid+1,r,x-(mid-l+1-sss),(root<<1)+1);
}
for(int i=1;i<=tt;i++)
{
int fff=fx(1,n,a[i],1,0);
upd(fff+n);
printf('%d ',fff);
}
試試吧 5.總結(jié)&感慨當初我為什么不用樹狀數(shù)組呢？因為線段樹的兩個子樹恰好都是一樣大小的，方便理解。 這玩意兒可以進行狀壓dp，求對應(yīng)下標以及還原成全排列時可以更快一些。 一個人想做出一道題，先要有足夠的自信。如果我當時把它當成一道紫題，那么我可能現(xiàn)在都沒寫出標程；但是，我一開始不知道它是紫題，也不知道它叫康托展開，只是看做一道黃題的線段樹優(yōu)化，對自己有足夠信心，就可以發(fā)揮你的潛力。 你如果愿意，還可以作死一些： 塊狀數(shù)組，O(N\sqrt{N}) 平衡樹，O(NlogN)
洛谷日報接受投稿，采用后有薄禮奉送,請戳 https://www./discuss/show/47327 .
|
