题目大意：
给你一个序列，对序列中所有逆序对之间连一条边，问图中最大独立集为多大，有哪些点一定在最大独立集中。思路：
在纸上画一下发现最大独立集一定是元序列的一个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#include #include #include inline int getint() { register char ch; while(!isdigit(ch=getchar())); register int x=ch^'0'; while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); return x; }const int N=100001;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,0,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=0; while(p) { ret=std::max(ret,val[p]); p-=lowbit(p); } return ret; }};FenwickTree t;int main() { n=getint(); for(register int i=1;i<=n;i++) { const int v=getint(); w[i]=v; id[v]=i; } for(register int i=1;i<=n;i++) { f[w[i]]=t.query(w[i])+1; t.modify(w[i],f[w[i]]); } t.reset(); for(register int i=n;i;i--) { g[w[i]]=t.query(n-w[i]+1)+1; t.modify(n-w[i]+1,g[w[i]]); } int ans=0; for(register int i=1;i<=n;i++) { ans=std::max(ans,f[w[i]]+g[w[i]]-1); } printf("%d\n",ans); for(register int i=1;i<=n;i++) { if(f[w[i]]+g[w[i]]-1==ans) { if(!~h[f[w[i]]]) continue; if(!h[f[w[i]]]) { h[f[w[i]]]=1; } else { h[f[w[i]]]=-1; } } } for(register int i=1;i<=n;i++) { if(f[w[i]]+g[w[i]]-1==ans&&h[f[w[i]]]==1) { printf("%d ",i); } } return 0;}