Skip to content

14100: 【原4100】Nene tchi’s Disaster

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4100 ## Description

现在是周五晚上六点,社畜梁青叶终于结束了某游戏公司一周的工作,准备回家洗洗睡了。但偏偏在这个时候,她的挚友兼隔壁码农部门的同事,程序姬殷宁宁跑来找她。原来宁宁姬一介法学生跑去初学C++,当然是各种术语听不懂,而且代码的时间复杂度和常数巨高,常常把她的上司气得脸色发黑;今天上司终于忍无可忍,给她布置了一打训练题让她两小时内做完(无偿加班),如果还看不懂或者又TLE,今晚就要把她抓去射击场当人肉靶子。没想到宁宁姬第一道题的题面就看不懂,于是跑来向青叶求救。题面仅仅只有一行字:

现有一个排列的所有前缀的逆序对数,输出所有符合要求的排列。

虽然青叶也看不懂题面,但青叶知道这些术语可以谷歌,查询结果如下:

排列:一个排列必然是一个序列,一个长度为\(N\)的排列(在没有特殊声明元素的情况下)则是指\(1\sim N\)这\(N\)个不重复的元素以任意顺序组成的一个序列。

前缀:一个长度为\(N\)的序列的长度为\(K \left( K \leq N \right)\)的前缀是指原序列的一个子序列,它包含原序列第\(1\sim K\)的所有元素。因此,一个长度为\(N\)的序列有\(N\)个前缀。

逆序对:一个序列的逆序对数是指这个序列中有多少对元素满足顺序上在前的元素大于在后的元素。亦即对于序列\(A[1..n]\),若存在正整数\(i, j\)使得\(1\leq i < j \leq n\) 而且 \(A[i] > A[j]\),则 \(\) 这个有序对称为A的一个逆序对;一个序列中逆序对的数量就是这个序列的逆序对数。

恶补了一套术语后,青叶终于看懂了题面。但其实青叶只是一个美工,根本不会C++,于是她把拯救宁宁姬的大任交给了你。

Input Format

第一行一个整数\(T\),为数据组数。(本题10大组数据,但每个大组数据下分T个小组,一个小组错误则该大组0分,时间限制为一个大组的时间限制。)

每一小组数据的第一行是一个整数\(N\),第二行有\(N\)个整数\(A_i\),表示长度为\(i\)的前缀的逆序对数。

Output Format

有T组输出,对应T组输入。

每一小组数据的第一行是一个整数\(M\),表示符合输入要求的排列有多少个; 接下来\(M\)行每行\(N\)个整数,表示一个符合输入要求的排列。

Sample Input

2
3
0 0 0
3
0 1 3

Sample Output

1
1 2 3
1
3 2 1

Data Range

对于\(30\%\)的数据,\(N \leq 10\)。

对于\(60\%\)的数据,\(N \leq 5000\)。

对于\(100\%\)的数据,\(1 \leq T \leq 5, 1 \leq N \leq 10^6\)。

这次评测机的性能和优化都很好,时限还两秒,常数不过分的话,多个把log也能轻松通过。

FineArtz's solution

/* Nene tchi's Disaster */
#include <iostream>
#include <cstring>
using namespace std;

class Node{
public:
    int l = 0, r = 0, sum = 0;

    Node() = default;
};

Node a[1000010 * 4];
long long b[1000010], ans[1000010];
int t, n;

void buildTree(int x, int l, int r){
    a[x].l = l;
    a[x].r = r;
    if (l == r)
        a[x].sum = 1;
    else{
        int mid = (l + r) / 2;
        buildTree(x * 2, l, mid);
        buildTree(x * 2 + 1, mid + 1, r);
        a[x].sum = a[x * 2].sum + a[x * 2 + 1].sum;
    }
}

int findk(int x, int k){
    if (a[x].l == a[x].r)
        return a[x].l;
    if (a[x * 2].sum >= k)
        return findk(x * 2, k);
    else
        return findk(x * 2 + 1, k - a[x * 2].sum);
}

void remove(int x, int k){
    if (a[x].l == a[x].r){
        a[x].sum = 0;
        return;
    }
    int mid = (a[x].l + a[x].r) / 2;
    if (k <= mid)
        remove(x * 2, k);
    else
        remove(x * 2 + 1, k);
    --a[x].sum;
}

void solve(){
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(ans, 0, sizeof(ans));
    cin >> n;
    buildTree(1, 1, n);
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
    for (int i = n; i > 1; --i){
        int d = b[i] - b[i - 1];
        ans[i] = findk(1, i - d);
        remove(1, ans[i]);
    }
    ans[1] = findk(1, 1);
    cout << 1 << endl;
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
}

int main(){
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}