E. Longest Increasing Subsequence
Bobo learned how to compute Longest Increasing Subsequence (LIS) in O(n log n) in ICPCCamp.
For those who did not attend ICPCCamp as Bobo, recall LIS(a1, a2, … , an) is defined as f[1]2 ⊕ f[2]2 ⊕
· · · ⊕ f[n]
2 where ⊕ denotes the exclusive-or (XOR) and f is calculated as follows.
for i in [1, 2, …, n]
f[i] = 1
for j in [1, 2, …, i - 1]
if a[j] < a[i] then
f[i] = max(f[i], f[j] + 1)
Given sequence A = (a1, a2, … , an), Bobo would like to find LIS(B1), LIS(B2), … , LIS(Bn) where Bi
is the
sequence after removing the i-th element from A.
Input
The input contains zero or more test cases and is terminated by end-of-file. For each test case:
The first line contains an integer n. The second line contains n integers a1, a2, … , an.
• 2 ≤ n ≤ 5000
• 1 ≤ ai ≤ n
• The number of test cases does not exceed 10.
Output
For each case, output n integers which denote LIS(B1), LIS(B2), … , LIS(Bn).
Sample Input
5
2 5 3 1 4
Sample Output
5 13 0 8 0
题意：给你一个长度为n的序列，问当删除第i个数后，剩余数的LIS的平方的异或和是多少。
题解：首先o（nlogn）预处理出以ai为结尾的LIS的长度。
然后对于每次删除的数ai来说，位于ai前面的LIS的长度不变，后面的要么不变，要么-1。现在判断长度是否-1，假设ai后面存在一个数aj，如果aj前面存在一个数ak（！=ai），使得ak的LIS==aj的LIS-1并且ak < aj.则删除ai后，对aj的LIS没有影响。如果想对于任意的aj都尽量满足没有影响，则ak的值尽可能小。所以用s[]维护长度为i 的最小结尾。
代码：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<int,int>pa;
const int N=1e5+10;
const int MOD=1e9+7;
const ll INF=1e18;
const int inf=1e4;
int read()
{
int x=0;
char ch = getchar();
while('0'>ch||ch>'9')ch=getchar();
while('0'<=ch&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x;
}
/************************************************************/
int n;
int a[N];
int dp[N];//记录以ai结尾的LIS的长度
int s[N];//记录长度为i的LIS的最小结尾
int f[N];//记录长度为i的LIS的结尾
void init()
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
fill(dp,dp+N-1,inf);
int cnt=0;
f[++cnt]=a[1];
dp[1]=cnt;
for(int i=2;i<=n;i++)
{
if(a[i]>f[cnt])
{
f[++cnt]=a[i];
dp[i]=cnt;
}
else
{
int pos=lower_bound(f+1,f+cnt,a[i])-f;
f[pos]=a[i];
dp[i]=pos;
}
}
}
int main()
{
while(~scanf("%d",&n))
{
init();
for(int i=1;i<=n;i++)
{
memset(s,0x3f3f3f3f,sizeof(s));
s[0]=0;
ll ans=0;
for(int j=1;j<i;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");
}
}