[CF340D]Bubble Sort Graph/[JZOJ3485]独立集

题目大意：
　　给你一个序列，对序列中所有逆序对之间连一条边，问图中最大独立集为多大，有哪些点一定在最大独立集中。

思路：
　　在纸上画一下发现最大独立集一定是元序列的一个LIS，最大独立集必经点就是所有LIS的公共部分。
　　考虑把所有的LIS记录下来，然后构建一个DAG，DAG的割点即为LIS的公共部分。
　　由于我们需要先知道所有的LIS的具体方案，只能写O(n^2)的DP记录转移，能拿60分。
　　不过事实上我们也不需要知道具体的状态。
　　我们可以记录一下所有LIS中的每个点在LIS上的哪个位置，看一下这个位置是否只有它一个点的。
　　如果不，那么肯定可以被别的点替代。
　　如果是，那么它肯定是LIS的公共部分。
　　LIS可以O(n log n)求，最后判断是O(n)的，总的时间复杂度是O(n log n)。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

inline int getint() {

    register char ch;

    while(!isdigit(ch=getchar()));

    register int x=ch^'';

    while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

    return x;

}

const int N=;

int w[N],id[N],f[N],g[N],h[N];

int n;

class FenwickTree {

    private:

        int val[N];

        int lowbit(const int &x) const {

            return x&-x;

        }

    public:

        void reset() {

            memset(val,,sizeof val);

        }

        void modify(int p,const int &x) {

            while(p<=n) {

                val[p]=std::max(val[p],x);

                p+=lowbit(p);

            }

        }

        int query(int p) const {

            int ret=;

            while(p) {

                ret=std::max(ret,val[p]);

                p-=lowbit(p);

            }

            return ret;

        }

};

FenwickTree t;

int main() {

    n=getint();

    for(register int i=;i<=n;i++) {

        const int v=getint();

        w[i]=v;

        id[v]=i;

    }

    for(register int i=;i<=n;i++) {

        f[w[i]]=t.query(w[i])+;

        t.modify(w[i],f[w[i]]);

    }

    t.reset();

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

        g[w[i]]=t.query(n-w[i]+)+;

        t.modify(n-w[i]+,g[w[i]]);

    }

    int ans=;

    for(register int i=;i<=n;i++) {

        ans=std::max(ans,f[w[i]]+g[w[i]]-);

    }

    printf("%d\n",ans);

    for(register int i=;i<=n;i++) {

        if(f[w[i]]+g[w[i]]-==ans) {

            if(!~h[f[w[i]]]) continue;

            if(!h[f[w[i]]]) {

                h[f[w[i]]]=;

            } else {

                h[f[w[i]]]=-;

            }

        }

    }

    for(register int i=;i<=n;i++) {

        if(f[w[i]]+g[w[i]]-==ans&&h[f[w[i]]]==) {

            printf("%d ",i);

        }

    }

    return ;

}

巴特西

[CF340D]Bubble Sort Graph/[JZOJ3485]独立集

最新文章

热门文章