http://www.lightoj.com/volume_showproblem.php?problem=1085

题意：求一个序列的递增子序列个数。

思路：找规律可以发现，某个数作为末尾数的种类数为所有比它小的数的情况+1。使用树状数组查找即可。 C++11 的auto在Lightoj上不能用/.\

/** @Date    : 2016-12-01-21.58  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const int mod = 1000000007;int C[N], a[N];void add(int p, int v){    while(p < N)    {        C[p] += v;        C[p] %= mod;        p += (-p) & p;    }}int sum(int p){    int ans = 0;    while(p)    {        ans += C[p];        ans %= mod;        p -= (-p) & p;    }    return ans;}int main(){    int T;    int cnt = 0;    cin >> T;    while(T--)    {        MMF(C);        int n;        scanf("%d", &n);        map<int , int>q;        for(int i = 1; i <= n; i++)        {            scanf("%d", &a[i]);            q[a[i]] = 1;        }        int c = 1;        for(auto i = q.begin(); i != q.end(); i++)            i->se = c++;        /*map<int , int>::iterator it;        for( it = q.begin(); it != q.end(); it++)            it->se = c++;*/        for(int i = 1; i <= n; i++)//找规律可以发现，某个数作为末尾数的种类数为所有比它小的数的情况+1        {            int x = q[a[i]];            add(x, sum(x - 1) + 1);        }        printf("Case %d: %d\n", ++cnt, sum(c - 1));    }    return 0;}

LightOJ 1085 - All Possible Increasing Subsequences 树状数组+离散