sichuan2017 E. Longest Increasing Subsequence(LIS变形)

时间:2022-08-13 19:27:03

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");
    }
}