51nod 1218 最长递增子序列

题面

给出一个序列，求哪些元素可能在某条最长上升子序列中，哪些元素一定在所有最长上升子序列中。

题解

YJY大嫂教导我们，如果以一个元素结尾的LIS长度 + 以它开头的LIS长度 - 1 = n，那么这个元素可能在LIS中。

那么什么时候它一定在呢？就是它在LIS中的位置“无可替代”的时候，即：设以它结尾的LIS长度为x，以任何其它元素（不可能在LIS中的元素除外）结尾的LIS长度均不为x。

然后就做出来了！

#include <cstdio>

#include <cstring>

#include <algorithm>

#define INF 0x3f3f3f3f

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

bool read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

	else if(c == EOF) return 0;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

    return 1;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 50005;

int n, a[N], s[N], cnt, lis[N], lds[N], type[N], tot[N];

int main(){

    read(n);

    for(int i = 1; i <= n; i++)

	read(a[i]);

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

	if(!cnt || a[i] > s[cnt]) s[++cnt] = a[i], lis[i] = cnt;

	else {

	    int pos = lower_bound(s + 1, s + cnt + 1, a[i]) - s;

	    s[pos] = a[i];

	    lis[i] = pos;

	}

    }

    cnt = 0;

    for(int i = 1; i <= n; i++)

	a[i] = -a[i];

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

	if(!cnt || a[i] > s[cnt]) s[++cnt] = a[i], lds[i] = cnt;

	else {

	    int pos = lower_bound(s + 1, s + cnt + 1, a[i]) - s;

	    s[pos] = a[i];

	    lds[i] = pos;

	}

    }

    for(int i = 1; i <= n; i++)

	if(lis[i] + lds[i] != cnt + 1) type[i] = 1;

	else tot[lis[i]]++;

    putchar('A'), putchar(':');

    for(int i = 1; i <= n; i++)

	if(!type[i] && tot[lis[i]] > 1)

	    write(i), space;

    enter;

    putchar('B'), putchar(':');

    for(int i = 1; i <= n; i++)

	if(!type[i] && tot[lis[i]] == 1)

	    write(i), space;

    enter;

    return 0;

}