pypy3(pypy3.6.1) 解法, 执行用时: 401ms, 内存消耗: 33320K, 提交时间: 2020-05-31 17:10:10

import math


def debug(*debugval):
    print("debug:   ", debugval)


t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    if n == 0:
        continue
    a = list(map(int, input().split()))
    mp = [0 for i in range(n + 1)]
    for i in range(n - 1):
        if a[i] > a[i + 1]:
            j = i
            while j - 1 >= 0 and a[j] == a[j - 1]:
                j -= 1
            for k in range(j,i+1):
                print(k + 1, end=' ')
            mp[i] = 1
    i = n - 1
    while i >= 0:
        j = i
        while j - 1 >= 0 and a[j] == a[j - 1]:
            j -= 1
        # debug(i, j)
        if mp[i] == 0:
            for k in range(j, i + 1):
                print(k + 1, end=' ')
        i = j - 1
    print()

C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 4080K, 提交时间: 2020-06-02 23:32:05

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;

int T;
int n,a[N],last[N],id[N];

bool cmp(int x,int y){
	if(x<y){
		if(last[x]>=y)return 1;
		return a[last[x]+1]<a[last[x]];
	}
	else{
		if(last[y]>=x)return 0;
		return a[last[y]]<a[last[y]+1];
	}
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i)scanf("%d",&a[i]);
		a[n+1]=-1;
		last[n+1]=n+1;
		for(int i=n;i;--i)
		if(a[i]==a[i+1])last[i]=last[i+1];
		else last[i]=i;
		for(int i=1;i<=n;++i)id[i]=i;
		sort(id+1,id+n+1,cmp);
		for(int i=1;i<=n;++i)printf("%d ",id[i]);
		printf("\n");
	}
} 

C++11(clang++ 3.9) 解法, 执行用时: 65ms, 内存消耗: 3960K, 提交时间: 2020-06-01 13:12:16

#include<bits/stdc++.h>
using namespace std;

int a[100005],pre[100005],Next[100005];
int main()
{
	int i,j,t,n;
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%d",&n);
    	pre[1]=0,Next[0]=1,Next[1]=n+1;
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		for(i=2;i<=n;i++)
		{
			if(a[i]<=a[i-1])j=i-1;
			else j=pre[i-1];
			Next[i]=Next[j],pre[Next[j]]=i,Next[j]=i;
			if(a[i]!=a[i-1])pre[i]=j;
			else pre[i]=pre[j];
		}
		for(i=Next[0];i<=n;i=Next[i])printf("%d ",i);
		printf("\n");
	}
}