题目大意：
给你一个序列，对序列中所有逆序对之间连一条边，问图中最大独立集为多大，有哪些点一定在最大独立集中。
思路：
在纸上画一下发现最大独立集一定是元序列的一个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 ;
}