OI周赛13-提高组

B题

题目大意:求一个由二元组组成最长序列，二元组的相对位置不变，并且满足对于数列a中任意一个数字
都是极大值或者极小值

首先离散将所有数字离散化.
分两种情况，奇数位较大和偶数为较大.
1.奇数位较大的情况， 我们需要将所有满足 x>y 的二元组选出来。用 表示前 i 个二元组选出的最后一个二元组的 y 小于等于 j 最多可以选出二元组的数量。由此可以写出状态转移方程：

这显然可以用个树状数组维护，树状数组维护以该数字结尾最优方案数，每次查询前缀最大值更新答案 ：

2.奇数位较小的情况，状态转移方程:

我们同样用树状数组维护，采用倒序插入的方式将后缀最小值转变为前缀最大值进行维护：

代码如下： 离散化用map偷懒

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=1e5+10;
int m1[maxn<<1],m2[maxn<<1];
int x[maxn],y[maxn];
int ans,t,tmp,n;
map<int,int>mp;

void change( int *a,int x,int c )
{
    while( x<=t )
    {
        a[x]=max(a[x],c);
        x+=lowbit(x);
    }
} 

int get_max( int *a,int x ) 
{
    int max1=0;
    while( x )
    {
        max1=max(max1,a[x]);
        x-=lowbit(x);
    } 
    return max1;
}

int main()
{
    scanf("%d",&n);
    for( int i=1;i<=n;i++ )
    {
        scanf("%d%d",&x[i],&y[i]);
        mp[x[i]]=1;
        mp[y[i]]=1;
    }
    for( auto &v:mp ) v.second=++t;
    for( int i=1;i<=n;i++ )
    {
        x[i]=mp[x[i]],y[i]=mp[y[i]];
        if( x[i]==y[i] ) continue;
        if( x[i]<y[i] )
        {
            tmp=get_max(m1,t-x[i])+1;
            ans=max(ans,tmp);
            change(m1,t-y[i]+1,tmp);
        }
        else
        {
            tmp=get_max(m2,x[i]-1)+1;
            ans=max(ans,tmp);
            change(m2,y[i],tmp);
        }
    }
    printf("%d",ans);
}