C++14(g++5.4) 解法, 执行用时: 1023ms, 内存消耗: 988K, 提交时间: 2019-10-05 16:07:34

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

int N;
int a[5010],f[5010],b[5010];

signed main () {

	while(scanf("%lld",&N) != EOF) {
		for(int i = 1;i <= N;++i)
			scanf("%lld",&a[i]);

		for(int i = 1;i <= N;++i) {
			f[i] = 1;
			for(int j = 1;j <= i - 1;++j)
				if(a[j] < a[i])
					  f[i] = max(f[i], f[j] + 1);
		}

		int pr = 0;
		for(int i = 1;i <= N;++i) {
			for(int j = 1;j <= N;++j)
				b[j] = 0x3f3f3f3f;
			b[0] = 0;

			int ans = 0;
			for(int j = 1;j <= N;++j) {
				if(j == i) continue;

				int t1 = f[j];
				if(b[t1 - 1] >= a[j]) {
					--t1;
				}

				b[t1] = min(b[t1],a[j]);
				ans ^= t1 * t1;

			}
			printf("%lld%c",ans," \n"[i == N]);
		}
	}
	//printf("%d\n",pr);
}

C++11(clang++ 3.9) 解法, 执行用时: 1956ms, 内存消耗: 1036K, 提交时间: 2019-10-05 20:15:02

#include <bits/stdc++.h>
using namespace std; 
const int N = 5005; 
int n, a[N], cf[N], f[N], g[N];  
int main(){
	while(~scanf("%d", &n)){
		for(int i=1; i<=n; ++i) scanf("%d", &a[i]); 
		for(int i=1; i<=n; ++i){
			cf[i] = 1; 
			for(int j=1; j<i; ++j)
				if(a[j] < a[i]) cf[i] = max(cf[i], cf[j]+1);  
		}
		for(int i=1; i<=n; ++i){
			long long ans = 0;  
			g[0] = INT_MIN;
			for(int j=1; j<=n; ++j) g[j] = INT_MAX; 
			for(int j=1; j<=n; ++j){
				if(j == i) continue; 
				f[j] = cf[j]; 
				if(g[f[j]-1] >= a[j]) --f[j]; 
				g[f[j]] = min(g[f[j]], a[j]); 
				ans = ans^(1ll*f[j]*f[j]); 
			}
			printf("%lld%c", ans, i==n?'\n':' '); 
		}
	}
	return 0; 
}