POJ 1631(O(nlogn)LIS的2种做法)

Language:
Bridging signals
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8574   Accepted: 4635

Description

对于一个二分图的完全匹配,请找出最多的边使其两两不相交。


Input

第一行为测试数据数t,
对于每组数据,第一行为匹配数 p < 40000,
接下来p行,每行1个数a[i],表示左边第i个端点与右边第a[i]个端点相连

Output

对每组数据,输出一行ans,表示最大不相交匹配数

Sample Input

4
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
8
8
7
6
5
4
3
2
1
9
5
8
9
2
3
1
7
4
6

Sample Output

3
9
1
4

Source

这题显然可以转化为a[i]的LIS

LIS的一般做法如下:

f[i]表示以i为最后一个元素的最长序列数,

f[i]=f[j]+1(a[j]<a[i],j<i)

nLogn 算法1:

显然上面的方程有1维n是用来求‘小于a[i]且在a[i]前面的,最大的数‘

单从这个定义考虑,

于是问题转化成-维护序列max(f[i]),每一次增加1个点的值,求[1,value_i)的最大值(若无值则为0)

不妨用一个zkw线段树维护(本题max(f[i])的长度=n,若没有这个条件时间会退化到O(nLogT)(T为a[i]的最大值),那么请把原序列排序O(nLogn)+离散化O(n),这样复杂度就有O(nLogT)降至O(nLogn)    ).

程序1如下:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (40000+10)
#define NDEBUG
int t,n;
struct SegMentTree
{
    int a[MAXN*10],n;
    int M;
    SegMentTree(){}
    SegMentTree(int _n):n(_n)
    {
        M=1;
        while (M-2<n) M<<=1;
        memset(a,0,sizeof(a));  
    }
    void insert(int _x,int c)
    {
        _x+=M;
        if (a[_x]<c)
        {
            a[_x]=c;
            for (_x>>=1;_x;_x>>=1) a[_x]=max(a[_x<<1],a[(_x<<1)^1]);
        }
    }
    int find(int l,int r)
    {
        int ans=0;
        l--;r++;
        l+=M;r+=M;
        while (l^r^1)
        {
            if (~l&1) ans=max(ans,a[l+1]);
            if (r&1) ans=max(ans,a[r-1]);
            l>>=1;r>>=1;
        }
        return ans;
    }
}a;
int main()
{
    #ifndef NDEBUG
    freopen("poj1631.in","r",stdin);
    #endif
    scanf("%d",&t);
    while (t--)
    {
        cin>>n;
        a=SegMentTree(n);
        for (int i=1;i<=n;i++)
        {
            int value;
            scanf("%d",&value);
            a.insert(value,a.find(1,value-1)+1);
        }   
        printf("%d\n",a.find(1,n));

    }   
    return 0;
}