题面下载：https://icpc-camp-cdn.b0.upaiyun.com/permanent/problems/sichuan-2017.pdf
题目大意：
给你N个数组成的序列，现在规定F【i】表示的是以a【i】结尾的最长上升子序列长度。
LIS（1）表示的是删除第一个数之后，F【i】的亦或和。
现在然你求LIS（1~N）；
思路：
删除第i个数，对他前边的数的F【j】没有影响，他后边的数的F【j】，要么还是F【j】，亦或者是F【j】-1；
那么我们首先nlogn去预处理出F【i】。
然后分两种情况考虑：
①当F【j】依旧为F【j】的时候，那么说明位子j前边存在某些位子使得F【x】=F【j】-1&&a【x】<a【j】&&x！=i（删除的位子）；
②当F【j】为F【j】-1的时候，就说明位子j前边没有存在那样的位子。
所以我们过程维护一个数组 s【Z】表示F值为Z的位子上最小的a【】；
就能贪心的使得s【Z】尽可能的小，那么满足F【j】依旧为F【j】的情况就越来越多了。
Ac代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long int
int a[5500];
int dp[5500];
int f[5500];
int s[5500];
int n;
void init()
{
memset(dp,0,sizeof(dp));
memset(f,0,sizeof(f));
memset(s,0,sizeof(s));
memset(a,0,sizeof(a));
int c=0;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
a[i]=t;
if(i==1)f[++c]=t,dp[i]=c;
else
{
if(t>f[c])f[++c]=t,dp[i]=c;
else
{
int pos=lower_bound(f+1,f+c,t)-f;//二分找到数组中比t大的第一个元素的的地址。
f[pos]=t;
dp[i]=pos;
}
}
}
}
int main()
{
while(~scanf("%d",&n))
{
init();
for(int i=1;i<=n;i++)
{
memset(s,0x7f,sizeof(s));
s[0]=0;
ll ans=0;
for(int j=1;j<=i-1;j++)
{
s[dp[j]]=min(s[dp[j]],a[j]);
ans^=((ll)dp[j]*(ll)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^=((ll)dp[j]*(ll)dp[j]);
}
else
{
s[dp[j]-1]=min(s[dp[j]-1],a[j]);
ans^=((ll)(dp[j]-1)*(ll)(dp[j]-1));
}
}
if(i!=1)printf(" ");
printf("%lld",ans);
}
printf("\n");
}
}