题目链接：
题目描述：
给出一个n个数的序列，问这个序列内严格递增序列有多少个？不要求连续
解题思路：
又遇到了用线段树来优化dp的题目，线段树节点里面保存所表达区间里面的方案数。先离散化序列(升序排列)，建树，然后按照没有sort前的顺序向线段树里面加点，每次查询小于该数的方案数目+1, 就是当前节点插入进去能影响的方案数目。在线段树对应位置加上新增加的数目即可。
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define lson 2*root
#define rson 2*root+1
typedef __int64 LL;
const LL mod = ;
const LL INF= 1e14+;
const int maxn = ; struct node
{
int l, r;
LL num;
int mid ()
{
return (l + r) / ;
}
} tree[maxn*];
LL a[maxn], b[maxn]; void build (int root, int l, int r)
{
tree[root].l = l;
tree[root].r = r;
tree[root].num = ;
if (l == r)
return ; build (lson, l, tree[root].mid());
build (rson, tree[root].mid()+, r);
}
void Insert (int root, LL x, int y)
{
if (tree[root].l == tree[root].r && tree[root].l == y)
{
tree[root].num =(tree[root].num + x) % mod;
return ;
} if (tree[root].mid() >= y)
Insert (lson, x, y);
else
Insert (rson, x, y);
tree[root].num = (tree[lson].num + tree[rson].num) % mod;
}
LL query (int root, int l, int r)
{
if (tree[root].l == l && tree[root].r == r)
return tree[root].num; if (tree[root].mid() >= r)
return query (lson, l, r);
else if (tree[root].mid() < l)
return query (rson, l, r);
else
{
LL num = ;
num += query (lson, l, tree[root].mid());
num += query (rson, tree[root].mid()+, r);
return num % mod;
}
} int main ()
{
int n; while (scanf ("%d", &n) != EOF)
{
for (int i=; i<n; i++)
{
scanf ("%I64d", &a[i]);
b[i] = a[i];
} sort (a, a+n);
int m = unique (a, a+n) - a; LL ans = ;
build (, , m);
for (int i=; i<n; i++)
{
LL nu, tmp = lower_bound (a, a+m, b[i]) - a;
if (tmp == )
nu = ;
else
nu = query (, , tmp-); Insert (, nu+, tmp);
} printf ("%I64d\n", query (, , m));
}
return ;
}
///4 1 2 2 3