题解：CF2144E2 Looking at Towers (difficult version)

· · 题解

容易先处理出 L(a) 和 R(a)，设元素个数分别为 cntL,cntR。

接下来考虑 DP。设 dp1_{i,j} 表示前 i 个数选了 L 中的前 j 个数的方案；dp2_{i,j} 表示后 i 个数选了 R 中的前 j 个数的方案。两者方程相似，故下面只对 dp1 进行讲解。

考虑转移，对于当前的数 a_i，以及 L 的前 j 个数已经被选择，可以分为以下三种情况：

当统计答案时，需要小心重复计算的情况。因此当 a_i 为全局最大值时，强制让 dp1 去选择这个最大值，然后强制 dp_2 不选这个最大值，则对答案的贡献为 (dp1_{i,cntL} - dp1_{i - 1,cntL}) \times dp2_{i + 1,cntR - 1}。

时间复杂度为 O(n^2)，代码如下：

void solve ()
{
    int n = read (),mx = 0;
    vector <int> a (n + 1),L (n + 1),R (n + 1);
    vector <vector <int>> dp1 (n + 1,vector <int> (n + 1)),dp2 (n + 2,vector <int> (n + 2));
    for (int i = 1;i <= n;++i) a[i] = read ();
    int cntL = 0,cntR = 0;
    for (int i = 1;i <= n;++i)
        if (mx < a[i]) L[++cntL] = a[i],mx = a[i];
    mx = 0;
    for (int i = n;i;--i)
        if (mx < a[i]) R[++cntR] = a[i],mx = a[i];
    dp1[0][0] = dp2[n + 1][0] = 1;
    for (int i = 1;i <= n;++i)
    {
        for (int j = cntL;~j;--j)
        {
            if (L[j] == a[i]) dp1[i][j] = (dp1[i - 1][j] * 2 % MOD + dp1[i - 1][j - 1]) % MOD;
            else if (L[j] > a[i]) dp1[i][j] = dp1[i - 1][j] * 2 % MOD;
            else dp1[i][j] = dp1[i - 1][j];
        }
    }
    for (int i = n;i >= 1;--i)
    {
        for (int j = cntR;~j;--j)
        {
            if (R[j] == a[i]) dp2[i][j] = (dp2[i + 1][j] * 2 % MOD + dp2[i + 1][j - 1]) % MOD;
            else if (R[j] > a[i]) dp2[i][j] = dp2[i + 1][j] * 2 % MOD;
            else dp2[i][j] = dp2[i + 1][j];
        }
    }
    ll ans = 0;
    for (int i = 1;i <= n;++i) 
    {
        if (a[i] != mx) continue;
        ans = (ans + 1ll * ((dp1[i][cntL] - dp1[i - 1][cntL] + MOD) % MOD) * dp2[i + 1][cntR - 1] % MOD) % MOD;
    }
    printf ("%lld\n",ans);
}

首先在 E1 的基础上可以滚动数组优化。其次，再次观察可以发现，每次的转移其实只是可根据与 a_i 的相对大小从而分为三类。

首先用 lower_bound 找到满足 L_x \ge a_i 这一条件最小的 x。若能够取等，则这一单点相当于可以从 x 和 x - 1 两个单点转移而来。对于 L_x > a_i 的，相当于进行区间乘 2 的操作；对于 L_x < a_i 的，相当于继承原有的值，不做任何处理即可。最后的答案，显然只需要将 cntL 与 cntR - 1 时候的值存下来，单点查询就能满足。

因此需要用能够实现区间乘，单点加，单点查询的数据结构维护，直接上线段树即可。时间复杂度优化为 O(n \log n)。

代码如下：

#include <bits/stdc++.h>
#define pii pair <int,int>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 3e5 + 5;
const int MOD = 998244353;
inline int read ();
int tree[MAX << 2],lazy[MAX << 2];
void pushdown (int cur)
{
    if (lazy[cur] == 1) return;
    tree[cur << 1] = 1ll * tree[cur << 1] * lazy[cur] % MOD;
    lazy[cur << 1] = 1ll * lazy[cur << 1] * lazy[cur] % MOD;
    tree[cur << 1 | 1] = 1ll * tree[cur << 1 | 1] * lazy[cur] % MOD;
    lazy[cur << 1 | 1] = 1ll * lazy[cur << 1 | 1] * lazy[cur] % MOD;
    lazy[cur] = 1;
}
void build (int cur,int l,int r)
{
    tree[cur] = 0;lazy[cur] = 1;
    if (l == r) {tree[cur] = l == 0;return ;}
    int mid = (l + r) >> 1;
    build (cur << 1,l,mid);build (cur << 1 | 1,mid + 1,r);
}
void modify1 (int cur,int l,int r,int x,int v)
{
    if (l == r) {tree[cur] = v;lazy[cur] = 1;return;}
    int mid = (l + r) >> 1;
    pushdown (cur);
    if (x <= mid) modify1 (cur << 1,l,mid,x,v);
    else modify1 (cur << 1 | 1,mid + 1,r,x,v);
}
void modify2 (int cur,int l,int r,int x,int y)
{
    if (x <= l && y >= r) {tree[cur] = tree[cur] * 2 % MOD;lazy[cur] = lazy[cur] * 2 % MOD;return;}
    int mid = (l + r) >> 1;
    pushdown (cur);
    if (x <= mid) modify2 (cur << 1,l,mid,x,y);
    if (y > mid) modify2 (cur << 1 | 1,mid + 1,r,x,y);
}
int query (int cur,int l,int r,int x)
{
    if (l == r) return tree[cur];
    int mid = (l + r) >> 1;
    pushdown (cur);
    if (x <= mid) return query (cur << 1,l,mid,x);
    else return query (cur << 1 | 1,mid + 1,r,x);
}
void solve ()
{
    int n = read (),mx = 0,cntL = 0,cntR = 0;
    vector <int> a (n + 1),L (n + 1),R (n + 1),ansl (n + 1),ansr (n + 2);
    for (int i = 1;i <= n;++i) a[i] = read ();
    for (int i = 1;i <= n;++i)
        if (mx < a[i]) L[++cntL] = a[i],mx = a[i];
    mx = 0;
    for (int i = n;i;--i)
        if (mx < a[i]) R[++cntR] = a[i],mx = a[i];
    build (1,0,cntL);
    L.resize (cntL + 1);R.resize (cntR + 1);
    for (int i = 1;i <= n;++i)
    {
        int id = lower_bound (L.begin (),L.end (),a[i]) - L.begin ();
        if (L[id] == a[i])
        {
            int dx = query (1,0,cntL,id),dy = query (1,0,cntL,id - 1);
            modify1 (1,0,cntL,id,(dx * 2 % MOD + dy) % MOD);
            ++id;
        }
        if (id <= cntL) modify2 (1,0,cntL,id,cntL);
        ansl[i] = query (1,0,cntL,cntL);
    }
    build (1,0,cntR);
    for (int i = n;i >= 1;--i)
    {
        int id = lower_bound (R.begin (),R.end (),a[i]) - R.begin ();
        if (R[id] == a[i])
        {
            int dx = query (1,0,cntR,id),dy = query (1,0,cntR,id - 1);
            modify1 (1,0,cntR,id,(dx * 2 % MOD + dy) % MOD);
            ++id;
        }
        if (id <= cntR) modify2 (1,0,cntR,id,cntR);
        ansr[i] = query (1,0,cntR,cntR - 1);
    }
    ll ans = 0;
    ansr[n + 1] = 1;
    for (int i = 1;i <= n;++i) 
    {
        if (a[i] != mx) continue;
        ans = (ans + 1ll * ((ansl[i] - ansl[i - 1] + MOD) % MOD) * ansr[i + 1] % MOD) % MOD;
    }
    printf ("%lld\n",ans);
}
int main ()
{
    int t = read ();
    while (t--) solve ();
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}