树状数组与LIS

求LIS的方法有很多，现在我知道的有三种，分别是dp， 贪心+二分，树状数组。这篇博客就重点写一点用树状数组解决LIS相关的题目。
预备知识：树状数组，离散化。
一个板子题：题目
我就简单的说一下用树状数组的思路：首先数据很大，很自然的想到离散化。然后树状数组维护什么呢？[1-i]（i为离散化后的相对大小）中以i结尾的LIS的长度，以为是1-i嘛，所以维护起来和普通的没什么两样。然后对于一个数a，离散化后它为i，那么我们就先求出 i-1 （想想为什么是i-1）结尾的LIS，再用这个结果+1去更新以 i 结尾的LIS的长度。如果还不理解就看看代码吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (int i = (n); i < (m); i++)
#define _rep(n,m,i) for (int i = (n); i <= (m); i++)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
int a[50010], n;
void update(int x, int y) {
  for(; x<=n; x += lowbit(x)) a[x] = max(a[x], y);
}
int query(int x) {
  int res = 0;
  for(; x; x -= lowbit(x)) res = max(res, a[x]);
  return res;
}
int b[50010];
vector<int>v;
inline int getid(int x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) {
    read(b[i]);
    v.push_back(b[i]);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  int ans = 0, num;
  for(int i = 1; i <= n; i++) {
    int id = getid(b[i]);
    num = query(id-1)+1;
    update(id, num);
    ans = max(ans, num);
  }
  cout << ans << endl;
}

提示，直接询问i求出来的是最长不下降子序列；
再来一个进阶题：题目
这题就是要求哪些数在LIS中一定会出现，那些数可能会出现。思路也很简单，求一遍最长递增子序列，再求一遍最长递减子序列，我们计f[i]，g[i]为以i结尾的最长递增，递减子序列的长度。if(f[i] + g[i] == LIS + 1) 那么这个数就可能在LIS中出现，对于不同的i，如果有相同的f[i]，那么些数在原来LIS中就是可能出现，反之就是一定出现。
这题的数字都是大于0的，所以求递减的子序列自需要把每个数取反，再反着求最长公共子序列就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (int i = (n); i < (m); i++)
#define _rep(n,m,i) for (int i = (n); i <= (m); i++)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
const int N = 1e5+5;
int a[N], n, cnt;
void update(int x, int y) {
  for(; x<=cnt; x += lowbit(x)) a[x] = max(a[x], y);
}
int query(int x) {
  int res = 0;
  for(; x; x -= lowbit(x)) res = max(res, a[x]);
  return res;
}
int b[N>>1], f[N>>1], g[N>>1], Hash[N>>1];
vector<int>v;
inline int getid(int x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main() {
  read(n);
  _rep(1,n,i) {
    read(b[i]);
    v.push_back(b[i]);
    v.push_back(-b[i]);
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  cnt = v.size();
  int ans = 0;
  _rep(1,n,i) {
    int id = getid(b[i]);
    f[i] = query(id-1)+1;
    update(id, f[i]);
    ans = max(ans, f[i]);
  }
  memset(a, 0, sizeof(a));
  for(int i = n; i >= 1; i--) {
    int id = getid(-b[i]);
    g[i] = query(id-1)+1;
    update(id, g[i]);
  }
  _rep(1,n,i) if(f[i] + g[i] == ans + 1) Hash[f[i]]++;
  printf("A:");
  _rep(1,n,i) if(f[i] + g[i] == ans + 1 && Hash[f[i]] > 1) printf("%d ", i);
  printf("\nB:");
  _rep(1,n,i) if(f[i] + g[i] == ans + 1 && Hash[f[i]] == 1) printf("%d ", i);
}

变形：求最长上升子序列的数量：题目意
歇一歇，晚点填坑！