51nod1218 最长递增子序列 V2

看见标签推荐顺便就做了吧

记$f[i], g[i]$为$i$的含$i$的前缀最长递增子序列和后缀递增子序列

只要满足$f[i] + g[i] == LIS + 1$，那么$i$就是可能的

对于$i$而言，其一定出现在$LIS$中时，当且仅当$f[i]$唯一

如果存在$i, j (i < j)$满足$f[i] = f[j]$，那么一定有$a[i] > a[j]$，这时这两者构成的$LIS$一定不相同

否则，如果$f[i]$唯一，那么所有$f$为$f[i] + 1$的点必须由它转移过来

注：树状数组打快了，结果$i += lowbit(i)$打成了$i ++$.........

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

extern inline char gc() {
    static char RR[23456], *S = RR + 23333, *T = RR + 23333;
    if(S == T) fread(RR, 1, 23333, stdin), S = RR;
    return *S ++;
}
inline int read() {
    int p = 0, w = 1; char c = gc();
    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
    return p * w;
}

#define ri register int
#define sid 50050

int n, cnp, H[sid * 2];
int f[sid], g[sid];
int t[sid], a[sid], v[sid];

inline int qry(int x) {
    int ret = 0;
    for(ri i = x; i; i -= i & (-i)) ret = max(ret, t[i]);
    return ret;
}

inline int mdf(int x, int v) {
    for(ri i = x; i <= cnp; i += i & (-i)) t[i] = max(t[i], v);
}

int num[sid];

int main() {
    n = read();
    for(ri i = 1; i <= n; i ++) {
        v[i] = read();
        H[i] = v[i]; H[i + n] = -v[i];
    }
    
    sort(H + 1, H + n + n + 1);
    cnp = unique(H + 1, H + n + n + 1) - H - 1;
    for(ri i = 1; i <= n; i ++)
    a[i] = lower_bound(H + 1, H + cnp + 1, v[i]) - H;
    
    for(ri i = 1; i <= n; i ++)
    f[i] = qry(a[i] - 1) + 1, mdf(a[i], f[i]);
    
    memset(t, 0, sizeof(t));
    for(ri i = 1; i <= n; i ++)
    a[i] = lower_bound(H + 1, H + cnp + 1, -v[i]) - H;
    
    for(ri i = n; i >= 1; i --)
    g[i] = qry(a[i] - 1) + 1, mdf(a[i], g[i]);
    
    int ans = 0;
    for(ri i = 1; i <= n; i ++) ans = max(ans, f[i]);
    
    for(ri i = 1; i <= n; i ++)
    if(f[i] + g[i] == ans + 1) num[f[i]] ++;
    printf("A:");
    for(ri i = 1; i <= n; i ++)
    if(f[i] + g[i] == ans + 1 && num[f[i]] > 1) printf("%d ", i);
    printf("
B:");
    for(ri i = 1; i <= n; i ++)
    if(f[i] + g[i] == ans + 1 && num[f[i]] == 1) printf("%d ", i);
    return 0;
}