CCPC-Wannafly Winter Camp Day3 (Div2, onsite) G 排列 思维 构造

G - 排列

搞清楚每个数组都是干什么的。

• P 原数组
• Ap 前缀数组
• q Ap中第i大的位置（相同的先取左边，例如 AP={2，1， 1}，第1小的位置是2而不是3.）

现在题目给了q，可以根据q倒推出Ap，然后倒推出P

include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn =1e5+10;
int a[maxn];
int q[maxn];
int main(){
    int n;
    scanf("%d",&n);
    int cnt=0;
    int pre=maxn+10;
    for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>pre)
		q[a[i]]=cnt;
		else
		q[a[i]]=++cnt;
		pre=a[i];
    }
    cnt=q[1];
    printf("%d ",cnt);
    for(int i=2;i<=n;i++){
        if(q[i]<q[i-1])
            printf("%d ",q[i]);
        else{
            printf("%d ",++cnt);

        }
    }
    return 0;
}