1748E Yet Another Array Counting Problem

目录
1748E Yet Another Array Counting Problem
题目大意：
做法
code

题目传送门

题目大意：

现在有一个长度为\(n\)的数组\(a\) , 现在你要找到一个数组\(b\)的每一个数都\(<= m\) 使得在\(n\)中的任意区间\([l , r]\)满足\(max_{i = l} ^ ra_i = max_{i = l} ^ rb_i\) 求方案数 $ mod 1e9 + 7$

做法

设\(dp_{pos , i}\)表示\(pos\)作为左边最大值的位置，且\(b_{pos} <= i\) 的方案数

显然\(dp_{pos , i} = \sum _{j = 1} ^ i dp_{lpos , j - 1} * dp_{rpos , j}\)

可以用线段树维护\(lpos、rpos\)

code

#include<bits/stdc++.h>

#define fu(x , y , z) for(int x = y ; x <= z ; x ++)

#define LL long long

using namespace std;

const int N = 2e5 + 5;

const LL mod = 1e9 + 7;

vector<LL> dp[N];

int a[N] , n , m , rt , tr[N << 2];

int read () {

    int val = 0 , fu = 1;

    char ch = getchar ();

    while (ch < '0' || ch > '9') {

        if (ch == '-') fu = -1;

        ch = getchar ();

    }

    while (ch >= '0' && ch <= '9') {

        val = val * 10 + (ch - '0');

        ch = getchar ();

    }

    return val * fu;

}

void build (int p , int l , int r) {

    if (l == r) {

        tr[p] = l;

    }

    else {

        int mid = l + r >> 1 , ll = p << 1 , rr = (p << 1) + 1;

        build (ll , l , mid) , build (rr , mid + 1 , r);

        if (a[tr[ll]] >= a[tr[rr]]) {

            tr[p] = tr[ll];

        }

        else

            tr[p] = tr[rr];

    }

}

int query (int p , int l , int r , int L , int R) {

    if (L <= l && R >= r) {

        return tr[p];

    }

    else {

        int mid = l + r >> 1 , ans1 = 0 , ans2 = 0 , ll = p << 1 , rr = (p << 1) + 1;

        if (L <= mid)

            ans1 = query (ll , l , mid , L , R);

        if (mid < R)

            ans2 = query (rr , mid + 1 , r , L , R);

        return a[ans1] >= a[ans2] ? ans1 : ans2;

    }

}

int dfs (int l , int r) {

    if (l > r)

        return -1;

    if (l == r) {

        fu(i , 1 , m)

            dp[l][i] = i;

        return l;

    }

    int id = query (1 , 1 , n , l , r);

    int ll = dfs (l , id - 1) , rr = dfs (id + 1 , r);

    if (ll == -1)

        fu(i , 1 , m)

            dp[id][i] = (dp[rr][i] + dp[id][i - 1]) % mod;

    else if (rr == -1)

        fu(i , 1 , m)

            dp[id][i] = (dp[ll][i - 1] + dp[id][i - 1]) %mod;

    else

        fu(i , 1 , m)

            dp[id][i] = (dp[ll][i - 1] * dp[rr][i] % mod + dp[id][i - 1]) % mod;

    return id;

}

int main () {

    int T = read ();

    while (T --) {

        n = read () , m = read ();

        fu(i , 1 , n) {

            a[i] = read ();

            dp[i].clear ();

            dp[i].resize(m + 1);

        }

        build (1 , 1 , n);

        rt = dfs (1 , n);

        printf ("%lld\n" , dp[rt][m]);

    }

    return 0;

}

1748E Yet Another Array Counting Problem的相关教程结束。