LightOJ 1085(树状数组+离散化+DP，线段树)

时间：2023-12-28 12:25:14
All Possible Increasing Subsequences

Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Appoint description: 

Description

An increasing subsequence from a sequence A1, A2 ... An is defined by Ai1, Ai2 ... Aik, where the following properties hold

  1. i1 < i2 < i3 < ... < ik and
  2. 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 ;

}

相关文章