Time Limit:3000MS Memory Limit:65536KB 64bit IO Format:%lld & %llu
Description
An increasing subsequence from a sequence A1, A2 ... An is defined by Ai1, Ai2 ... Aik, where the following properties hold
- i1 < i2 < i3 < ... < ik and
- 2. Ai1 < Ai2 < Ai3 < ... < Aik
Now you are given a sequence, you have to find the number of all possible increasing subsequences.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case contains an integer n (1 ≤ n ≤ 105) denoting the number of elements in the initial sequence. The next line will contain n integers separated by spaces, denoting the elements of the sequence. Each of these integers will be fit into a 32 bit signed integer.
Output
For each case of input, print the case number and the number of possible increasing subsequences modulo 1000000007.
Sample Input
3
3
1 1 2
5
1 2 1000 1000 1001
3
1 10 11
Sample Output
Case 1: 5
Case 2: 23
Case 3: 7
题解：让求单调递增序列的个数；dp[i]=sum(dp[j])+1(j<i);由于数太大，需要离散化由于是单调的，所以当相等的时候树状数组要从大到小inset,以免对后面相等的造成影响，还可以用线段树写；
树状数组：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int MOD=;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+;
int dp[MAXN],a[MAXN],p[MAXN];
int N;
int lowbit(int x){return x&(-x);}
void insert(int x,int v){
while(x<=N){
dp[x]=(dp[x]+v)%MOD;
x+=lowbit(x);
}
}
int sum(int x){
int ans=;
while(x>){
ans=(ans+dp[x])%MOD;
x-=lowbit(x);
}
return ans;
}
int cmp(int x,int y){
if(a[x]!=a[y])return a[x]<a[y];
else return x>y;
}
int main(){
int T,kase=;
SI(T);
while(T--){
SI(N);
for(int i=;i<=N;i++)SI(a[i]),p[i]=i;
sort(p+,p+N+,cmp);
mem(dp,);
for(int i=;i<=N;i++){
insert(p[i],sum(p[i])+);
}
printf("Case %d: %d\n",++kase,sum(N));
}
return ;
}
线段树：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define SI(x) scanf("%d",&x)
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int MOD=;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+;
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define ll root<<1
#define rr root<<1|1
int tree[MAXN<<],p[MAXN],a[MAXN];
int ans=;
void pushup(int root){
tree[root]=(tree[ll]+tree[rr])%MOD;
}
void insert(int root,int l,int r,int flog,int v){
int mid=(l+r)>>;
if(l==flog&&r==flog){
tree[root]=v;
return;
}
if(mid>=flog)insert(lson,flog,v);
if(mid<flog)insert(rson,flog,v);
pushup(root);
}
void sum(int root,int l,int r,int L,int R){
int mid=(l+r)>>;
if(l>=L&&r<=R){
ans=(ans+tree[root])%MOD;
return;
}
if(mid>=L)sum(lson,L,R);
if(mid<R)sum(rson,L,R);
return;
}
int cmp(int x,int y){
if(a[x]!=a[y])return a[x]<a[y];
else return x>y;
}
int main(){
int T,N,kase=;
SI(T);
while(T--){
SI(N);
for(int i=;i<=N;i++)SI(a[i]),p[i]=i;
sort(p+,p+N+,cmp);
mem(tree,);
for(int i=;i<=N;i++){
ans=;
sum(,,N,,p[i]);
insert(,,N,p[i],ans+);
}
printf("Case %d: %d\n",++kase,tree[]);
}
return ;
}