[atAGC052D]Equal LIS

令$f_{i}$表示以$i$为结尾的最长上升子序列，显然可以快速预处理

令$L=\max_{i=1}^{n}f_{i}$，当$L$为偶数，考虑如下构造——

将所有$f_{i}\le \frac{L}{2}$的$a_{i}$选入第1个序列，其余位置选入第2个序列

此时，来证明两个序列的最长上升子序列都是$\frac{L}{2}$

考虑这个长为$L$的最长上升子序列，其前$\frac{L}{2}$个元素必然都在第1个序列中，后$\frac{L}{2}$个元素必然都在第2个序列中，即两者最长上升子序列长度都大于等于$\frac{L}{2}$

另一方面，第1个序列中以$i$为结尾的最长上升序列小于等于$\frac{L}{2}$，第2个序列中以$i$为起点的最长上升序列小于等于$\frac{L}{2}$（由于$f_{i}>\frac{L}{2}$，且两者之和小于等于$L$，即有此结论），也都小于等于$\frac{L}{2}$

（其中$i$为各自序列中任意元素）

当$L$为奇数，假设$L=2k+1$，那么对于其中一个长为$L$的上升子序列，要存在一个元素$x$，其不在此序列中，且存在一个长为$k+1$的上升子序列包含其

关于这件事情的必要性是显然的，同时其也是充分的，考虑如下构造——

任选一个长为$L$的上升子序列，根据此性质，选择$x$并假设这个$k+1$的上升子序列为$p_{1},p_{2},...,p_{k+1}$

将所有满足$\forall 1\le j\le k+1,f_{i}\ne f_{p_{j}}$或$f_{i}=f_{x}$且$i\ne x$的$a_{i}$选入第1个序列，其余位置选入第2个序列

在第1个序列中，考虑这个长为$L$的上升子序列，设其中第$i$个位置为$x$，即有$f_{x}=i$，恰好包含$[1,L]$中所有值，其中恰有$k$个值不能选（$f_{i}=f_{x}$是可以选的），构成一个长为$k+1$的上升子序列

在第2个序列中，$p_{i}$都被选入第2个序列，也构成一个长为$k+1$个上升子序列

另一方面，对于一个长为$k$的上升子序列，每一个位置的$f_{x}$必然各不相同，而注意到两个序列中都至多含有$k+1$个不同的$f$，即不存在长为$k+2$的上升子序列

关于判定，求出以每一个元素为起点和终点的最长上升子序列，即可求出强制包含某个元素的最长上升子序列，判定其是否大于等于$k+1$即可

由此，即解决此问题，时间复杂度为$o(n\log n)$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define L (k<<1)

 5 #define R (L+1)

 6 #define mid (l+r>>1)

 7 int t,n,ans,a[N],vis[N],f[N],g[N],mx[N<<2];

 8 void build(int k,int l,int r){

 9     mx[k]=0;

10     if (l==r)return;

11     build(L,l,mid);

12     build(R,mid+1,r);

13 }

14 void update(int k,int l,int r,int x,int y){

15     if (l==r){

16         mx[k]=y;

17         return;

18     }

19     if (x<=mid)update(L,l,mid,x,y);

20     else update(R,mid+1,r,x,y);

21     mx[k]=max(mx[L],mx[R]);

22 }

23 int query(int k,int l,int r,int x,int y){

24     if ((l>y)||(x>r))return 0;

25     if ((x<=l)&&(r<=y))return mx[k];

26     return max(query(L,l,mid,x,y),query(R,mid+1,r,x,y));

27 }

28 int main(){

29     scanf("%d",&t);

30     while (t--){

31         scanf("%d",&n);

32         for(int i=1;i<=n;i++)scanf("%d",&a[i]);

33         ans=0;

34         build(1,1,n);

35         for(int i=1;i<=n;i++){

36             f[i]=query(1,1,n,1,a[i]-1)+1;

37             update(1,1,n,a[i],f[i]);

38             ans=max(ans,f[i]);

39         }

40         if (ans%2==0)printf("YES\n");

41         else{

42             build(1,1,n);

43             for(int i=n;i;i--){

44                 g[i]=query(1,1,n,a[i]+1,n)+1;

45                 update(1,1,n,a[i],g[i]);

46             }

47             bool flag=0;

48             for(int i=n,j=ans;i;i--)

49                 if (f[i]==j)j--;

50                 else{

51                     if (f[i]+g[i]-1>=ans/2+1){

52                         printf("YES\n");

53                         flag=1;

54                         break;

55                     }

56                 }

57             if (!flag)printf("NO\n");

58         }

59     }

60 }

巴特西

[atAGC052D]Equal LIS

最新文章

热门文章