51nod 1376 DP BIT

题

题意：求 LIS 的数量。

解

之前就思考过这个问题，总觉得不能用 $ O(n \lg n) $ 的方法做……
然后 @lhz 在知乎上发现了一个答案说可以用数据结构（线段树/树状数组）维护，而 @xbw 说并无需，跑一遍求出 LIS 的长度后再跑一遍记录转移。
然而实际上用数据结构更好写？？反正我也是看了别人题解才会的……

离散化后按值域建树状数组，顺原数组向跑一遍，值为 $ x $ 的点的 LIS 信息一定可以由 $ [1, x-1] $ 的转移得到。（当然我在这里还是想谈一谈本质思想：事实上几乎所有值域数据结构即是把索引/值二维映射到时间/值二维）。
有什么要记录的 LIS 信息呢。
LIS 的长度和数量，考虑转移

$$ \begin{cases} I[i].max =& \max_{j<i且a[j]<a[i]} I[j].max \\\\ I[i].cnt =& 1+\sum_{j<i且a[j]<a[i]且I[i].max=I[j].max} I[j].cnt \end{cases} $$

而 $ a[j]<a[i] $ 意味着在 BIT 的增加时间中 $ j $ 比 $ i $ 前，即时间维中更早，所以在时间/值域 BIT 中不必多做处理。
总的复杂度还是 $ O(n \lg n) $ 的。

据说还可以 cdq 分治，待研究（又是一个坑）。

码（62ms, 3468K）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 5e4 + 1000, mod = 1e9 + 7;
int n;
struct Info
{
    int _max, cnt;
    Info(int a = 0, int b = 0) : _max(a), cnt(b) {}
    Info operator+(const Info& rhs)
    {
        return _max < rhs._max ? rhs : Info(_max, (_max == rhs._max) ? (cnt + rhs.cnt) % mod : (cnt));
    }
} I[maxn * 3];
void update(int u, Info x)
{
    for(int i = u; i <= n; i += i & -i)
        I[i] = I[i] + x;
}
Info query(int u)
{
    Info ret(0, 1);
    for(int i = u; i > 0; i -= i & -i)
        ret = ret + I[i];
    return ret;
}
int a[maxn] = {0}, b[maxn] = {0};
int main()
{
    read(n);
    for(int i = 1; i <= n; i++)
    {
        read(a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b;
    for(int i = 1; i <= n; i++)
    {
        int x = lower_bound(b + 1, b + m + 1, a[i]) - b;
        Info cur = query(x - 1);
        update(x, Info(cur._max + 1, cur.cnt));
    }
    printf("%d\n", query(n).cnt);
    return 0;
}