[51Nod 1218] 最長遞增子序列 V2 (LIS)

傳送門

Description

數組A包含N個整數。設S為A的子序列且S中的元素是遞增的，則S為A的遞增子序列。如果S的長度是所有遞增子序列中最長的，則稱S為A的最長遞增子序列（LIS）。A的LIS可能有很多個。例如A為：1 3 2 0 4，1 3 4，1 2 4均為A的LIS。其中元素1和4一定會出現在LIS當中，元素2和3可能會出現在LIS當中，元素0一定不會出現在LIS當中。給出數組A，輸出哪些數可能出現在LIS中，哪些數一定出現在LIS中。輸出數字對應的下標，下標編號從1開始，編號為1 - N。例如：1 3 2 0 4，可能出現的元素為3和2，對應的下標為2和3。一定出現的元素為1和4，對應下標為1和5.

Input

第1行：1個數N，表示數組的長度。(1 <= N <= 50000)
第2 - N + 1行：每行1個數A[i]，表示數組的元素(0 <= A[i] <= 10^9)

Output

第1行：可能出現在LIS中的數的下標，中間用空格分隔。（輸出的下標按照遞增排序）
第2行：一定會出現在LIS中的數的下標，中間用空格分隔。（輸出的下標按照遞增排序）

Sample Input

5
1
3
2
0
4

Sample Output

A:2 3
B:1 5

Solution

正的跑最長上升子序列，反的跑最長下降子序列
如果正反的dp值相加等于len+1(自己加了兩次)說明可能在LIS中
若dp值獨一無二且可能出現即為一定出現

Code

//By Menteur_Hxy
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define F(i,a,b) for(register int i=(a);i<=(b);i++)
#define R(i,a,b) for(register int i=(b);i>=(a);i--)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)
using namespace std;char buf[1<<21],*p1,*p2;
inline int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f;
}const int N=50010;
int n,len;
bool vis1[N],vis2[N];
int a[N],s[N],f[N],g[N];
vector<int> V[N];int main() {n=read();F(i,1,n) a[i]=read();F(i,1,n) {if(s[len]<a[i]) s[++len]=a[i],f[i]=len;else {int tmp=lower_bound(s+1,s+1+len,a[i])-s;s[tmp]=a[i];f[i]=tmp;}}len=0;R(i,1,n) {if(s[len]<-a[i]||!len) s[++len]=-a[i],g[i]=len;//無腦取負qwqelse {int tmp=lower_bound(s+1,s+1+len,-a[i])-s;s[tmp]=-a[i];g[i]=tmp;}}F(i,1,n) {if(f[i]+g[i]==len+1) vis1[i]=1;if(vis1[i]) V[f[i]].push_back(i);}F(i,1,n) {int siz=V[i].size();if(siz==1) vis2[V[i][0]]=1;}// F(i,1,n) cout<<f[i]<<" ";cout<<endl;// F(i,1,n) cout<<g[i]<<" ";cout<<endl;putchar('A');putchar(':'); F(i,1,n) if(vis1[i]&&!vis2[i]) printf("%d ",i);putchar('\n');putchar('B');putchar(':'); F(i,1,n) if(vis2[i]) printf("%d ",i);return 0;
}