树状数组版本。
完整版
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[100009],fac[10009];
bool vis[100009];
ll tree[100009];
ll lowbit(int x){return x&(-x);}
void add(ll x,ll w){
while(x<=n){
tree[x]+=w;
x+=lowbit(x);
}
}
ll ask(ll x){
ll ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void kangtuo()
{
ll ans=0;
for(int i=1;i<=n;i++) add(i,1);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
add(a[i],-1);//划掉这个数
ans+=ask(a[i])*fac[n-i];//找前面有几个比自己小的数
}
cout<<ans+1<<endl;
}
void nikangtuo()
{
memset(vis,0,sizeof(vis));
ll rank;
cin>>rank;rank--;
for(ll i=1;i<=n;i++)
{
ll temp=rank/fac[n-i];//把过程逆转回去,找第temp大的
for(ll j=1;j<=n;j++)
{
if(vis[j]) continue;
if(temp==0)
{
cout<<j<<" ";
vis[j]=1;
break;
}
temp--;
}
rank%=fac[n-i];
}
cout<<endl;
}
int main()
{
char s;
cin>>n>>m;
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
for(int i=1;i<=m;i++)
{
cin>>s;
if(s=='P') nikangtuo();
else kangtuo();
}
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int tree[1000009],a[1000009],n;
int lowbit(int x){
return x&(-x);
}
int ask(int x){
int ans=0;
while(x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
void add(int x,int k){
while(x<=n){
tree[x]+=k;
x+=lowbit(x);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int x=a[i]-ask(a[i]);
add(a[i],1);
a[i]=x-1;
}
ll ans=0;
for(int i=1;i<n;i++)
ans=(ans+a[i])*(n-i)%mod;
cout<<(ans+1)%mod;
}
逆康托展开(还看不懂)
LL Check(LL l,LL r,LL aim) {
while(l < r) {
LL mid = (l + r) >> 1;
if(query(mid) - 1 >= aim) {
r = mid;
} else {
l = mid + 1;
}
}
return r;
}
void reCantor() {
pos --; // 需要先 -- (排名从 0 开始)
for(LL i = 1,num = n - 1; i <= n; num --, i ++) {
LL aim = pos / fac[num]; // 找 第 k 大的数
pos = pos % fac[num];
LL t = Check(1,n,aim);
cout << t << " ";
add(t ,-1); // 与上面的解释一样
}
cout << endl;
return ;
}