题意:
给你N个数组成的序列，现在规定F【i】表示的是以a【i】结尾的最长上升子序列长度。
LIS（1）表示的是删除第一个数之后，F【i】的亦或和。
现在然你求LIS（1~N）；
思路:
考虑我们如果删除第i个数，F【】的变化.
首先对于i前面的数,F【】都不会有影响.
那么对于i后面的数,他的F[j] 只会有两种情况,
1、如果存在一个数x,使其满足 F【x】=F[j]-1&&x!=i&&a[x]<a[j] 那么这个删除i后他的F仍为F[j]
2.如果不存在上面这样的数,那么F变为F【j】-1;
那么我们开一个数组s,s【len】表示当前长度最长上升子序列为len的,最后的那个元素最小是多少.那么这样
当我们要删除第i个元素的时候,就可以判断当前i的删除对j的整个上升序列是否有影响,然后维护一下s的最小值就好.
贪心的维护s的最小值,使得F,尽可能的还为F【j】
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e4+10;
int n;
int a[maxn];
int dp[maxn];
int s[maxn];
int main(){
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<=i-1;j++)
{
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
//memset(s,0,sizeof(s));
ll ans=0;
for(int i=1;i<=n;i++)
{
memset(s,inf,sizeof(s));
ans=0;
s[0]=0;
for(int j=1;j<=i-1;j++)
{
s[dp[j]]=min(s[dp[j]],a[j]);
ans^=(dp[j]*dp[j]);
}
for(int j=i+1;j<=n;j++)
{
if(a[j]>s[dp[j]-1])
{
s[dp[j]]=min(s[dp[j]],a[j]);
ans^=(dp[j]*dp[j]);
}
else
{
s[dp[j]-1]=min(s[dp[j]-1],a[j]);
ans^=((dp[j]-1)*(dp[j]-1));
}
}
if(i!=1)printf(" ");
printf("%lld",ans);
}
puts("");
}
return 0;
}