hdu6078 Wavel Sequence dp+二维树状数组

//#pragma comment(linker, "/STACK:102400000,102400000")

/**

题目：hdu6078 Wavel Sequence

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6078

题意：给定a序列和b序列。从a中取一个子序列x（数的位置顺序保持不变），子序列每个数满足a1<a2>a3<a4>a5<a6...  波浪形

从b中取相同长度的子序列y，也满足波浪形。 如果x与y序列一模一样，那么找到一个匹配方式。

求a与b两个序列有多少种匹配方式（相同的数但不同的位置，那么算作不同）。

思路：

定义dp[i][j][k]表示x序列以a[i]为结尾，y序列以b[j]结尾，k=0表示a[i]是波谷，k=1表示a[i]是波峰时候的匹配方式。

容易想到

dp[i][j][0] = sigma(dp[x][y][1]), x<i,y<j,b[x]>b[i];    （a[i]==b[j],a[x]==b[y]）

dp[i][j][1] = sigma(dp[x][y][0]), x<i,y<j,b[x]<b[i];

由于i的枚举是最外围循环，所以当前这个i要得到的结果来源前面计算过的，一定满足x<i.所以x<i不用作为限制因素。

现在要考虑满足y<j,b[x]>b[i]||b[x]<b[i]; 所以用二维树状数组维护y和b[x]。

定义c[j][value][k]表示y序列的结尾下标在j以内，数值大小value以内，波浪状态为k时候的匹配方式数。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<time.h>

#include<random>

#include<cmath>

using namespace std;

typedef pair<int,int> P;

typedef long long LL;

const int mod = ;

const int INF = 0x3f3f3f3f;

const int N = ;

int n, m;

int a[N], b[N];

int dp[N][];

int c[N][N][];

///二维树状数组

int query(int i,int j,int flag)

{

    int s = ;

    for(int x = i; x > ; x-=(x&(-x))){

        for(int y = j; y > ; y-=(y&(-y))){

            s = (s+c[x][y][flag])%mod;

        }

    }

    return s;

}

void update(int i,int j,int flag,int d)

{

    for(int x = i; x <= ; x+=(x&(-x))){

        for(int y = j; y <= ; y+=(y&(-y))){

            c[x][y][flag] = (c[x][y][flag]+d)%mod;

        }

    }

}

int main()

{

    int T;

    cin>>T;

    for(int i = ; i<T; i++)

    {

        scanf("%d%d",&n,&m);

        for(int i = ; i <= n; i++) scanf("%d",&a[i]);

        for(int i = ; i <= m; i++) scanf("%d",&b[i]);

        memset(c, , sizeof c);

        LL ans = ;

        for(int i = ; i <= n; i++){

            for(int j = ; j <= m; j++){

                if(a[i]!=b[j]) continue;

                dp[j][] = (query(j,,)-query(j,b[j],)++mod)%mod;///+1是因为每一个b[j]都可以单独自身作为波谷，成为一个序列。

                dp[j][] = query(j,b[j]-,);

                ans = (ans+dp[j][]) %mod;

                ans = (ans+dp[j][]) %mod;

                update(j,b[j],,dp[j][]);

                update(j,b[j],,dp[j][]);

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}