题解 UVA11525 【Permutation】

· · 题解

注意行末无空格！！！

本蒟蒻采用树状数组+倍增的方法，之前也有大佬这样写，但我的切入方式和他的略有不同，故发一篇题解，希望能帮到大家。

在此默认已经会了康托展开，不会的同学先看这道题。

先看这个式子：（题面Markdown挂了很难受）

n=\sum_{i=1}^k S_i*(k-i)!

根据简单的数学排列组合思想，(k-i)!指的是第i位后的数字全排列的个数，也就是说这些全排列字典序均小于待求序列。

这就要求第i位的数字小于实际第i为的数字a[i]，所以题中的S[i]指的是原序列第i位后的数字比a[i]小的数字的个数。

很多同学可能会想到权值线段树或者平衡树，可我太弱了，只会树状数组。

本意是想用二分答案，因为要填的数字a[i]越大，之后比它小的数就会越多，显然具有可二分性。

其实这样也可以倍增来解决。

虽然比权值线段树多一个log，但还是比较快的，没有刻意卡常，60ms，加上快输应该会再快一点。

有一个小细节，就是在query()函数中，所查询的可能大于k，所以树状数组不能卡边开5e4，应该开到2^{log_2k+1}，我直接开到2e5了

下面是代码：（略有压行，不喜勿喷）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int T,n,N,c[maxn],po[20]={1};
inline void modify(int x,int delta) {for(;x<=n;x+=x&-x) c[x]+=delta;}
inline int query(int x,int res=0) {for(;x;x-=x&-x) res+=c[x];return res;}
inline int gint() {
    char ch=getchar();int s=0,f=1;
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
inline int work(int x,int res=0) {
    //query(res+po[i]),即为已填过的比当前将要填的数小的数的个数 
    //res+po[i]-query(res+po[i])-1即为未填的比当前树小的数的个数 
    for(int i=N;~i;i--) if(res+po[i]-query(res+po[i])<=x) res+=po[i];
    return res+1;
}
int main() {
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    T=gint();
    for(int i=1;i<=16;i++) po[i]=po[i-1]<<1;
    while(T--) {
        n=gint();memset(c,0,sizeof c);N=log2(n); 
        for(int i=1,x;i<=n;i++) {
            x=gint();int k=work(x);
            modify(k,1);
            printf("%d",k);
            if(i!=n) putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}

感谢您的阅读

如果对您有帮助，请在右上角点一个赞