题解：P12646 [KOI 2024 Round 1] 升序

· · 题解

火箭滑板毛毛虫。

考虑求出 hi_i = \lfloor \log_2 a_i \rfloor, ex_i = [a_{i-1} \times 2^{\max(hi_i - hi_{i-1}, 0)} > a_i \times 2^{\max(hi_{i-1} - hi_i, 0)}]，即 a_i 二进制下最高位，和若 a_{i-1},a_i 被乘到最高位相同，a_i 是否需要多乘一步来保证不降。

那么考虑对每个询问从 l 到 r 依次加入每个数，维护当前最后一个数被乘之后的最高位 pr 和答案 sm，加入 a_i 时先后令 pr \larr \max(hi_i, pr+ex_i), sm \larr sm + pr - hi_i。

发现这是历史和状物，于是考虑对右端点扫描线，使用线段树维护左端点对应的答案，(\times,+) 矩阵刻画信息。

考虑去掉 \max，可以发现 pr_l 关于 l 不增，于是用单调栈维护 pr_l 的连续段即可，需要维护标记表示栈内 ex_i 的增量。

复杂度 O(n\log{n}\operatorname{M})，其中 O(\operatorname{M}) 表示单次矩阵乘法的复杂度。

若直接使用 3\times3 的矩阵可能难以通过，考虑一些经典卡常技巧，比如循环展开，去掉不变量。

constexpr int N = 25e4 + 5, M = N << 2;

int n, q;
int arr[N];
vector <array <int, 2>> qry[N];
array <int, 2> stk[N];
LL res[N];

struct mat
{
    LL v1, v2, v3, v4, v5;
    friend mat operator*(mat a, mat b)
    {
        mat c;
        c.v1 = a.v1 * b.v1 + a.v3 * b.v4;
        c.v2 = a.v1 * b.v2 + a.v2 + a.v3 * b.v5;
        c.v3 = a.v1 * b.v3 + a.v3;
        c.v4 = a.v4 * b.v1 + b.v4;
        c.v5 = a.v4 * b.v2 + a.v5 + b.v5;
        return c;
    }
}
val[M], tag[M];
int vis[M];

#define lp (p << 1)
#define rp (p << 1 | 1)
#define m (l + r >> 1)

void update(int p, mat v)
{
    val[p] = val[p] * v;
    tag[p] = vis[p] ? tag[p] * v : v;
    vis[p] = 1;
}

void build(int p = 1, int l = 1, int r = n)
{
    val[p].v3 = tag[p].v1 = 1;
    if (l < r) build(lp, l, m), build(rp, m + 1, r);
}

void modify(int L, int R, mat v, int p = 1, int l = 1, int r = n)
{
    if (r < L || l > R) return;
    if (l >= L && r <= R) return update(p, v);
    if (vis[p]) update(lp, tag[p]), update(rp, tag[p]), vis[p] = 0;
    modify(L, R, v, lp, l, m), modify(L, R, v, rp, m + 1, r);
}

LL query(int k, int p = 1, int l = 1, int r = n)
{
    if (l == r) return val[p].v2;
    if (vis[p]) update(lp, tag[p]), update(rp, tag[p]), vis[p] = 0;
    return k <= m ? query(k, lp, l, m) : query(k, rp, m + 1, r);
}

#undef lp
#undef rp
#undef m

int check(int x, int y)
{
    int t = __lg(y) - __lg(x);
    x <<= max(t, 0), y <<= max(-t, 0);
    return x > y;
}

void mainSolve()
{
    read(n, q);
    for (int i = 1; i <= n; i ++) read(arr[i]);
    for (int i = 1; i <= q; i ++)
    {
        int l, r; read(l, r);
        qry[r].push_back({l, i});
    }

    int top = 0, cnt = 0; mat v;
    build(), v.v1 = 1, v.v2 = v.v3 = v.v4 = v.v5 = 0;
    for (int r = 1; r <= n; r ++)
    {
        int h = __lg(arr[r]);
        while (top && stk[top][0] + cnt < h)
        {
            v.v4 = h - stk[top][0] - cnt;
            modify(stk[top - 1][1] + 1, stk[top][1], v);
            v.v4 = 0, --top;
        }
        if (r > 1 && check(arr[r - 1], arr[r]) && top)
            ++cnt, v.v4 = 1, modify(1, stk[top][1], v), v.v4 = 0;
        v.v4 = h, modify(r, r, v), v.v4 = 0, stk[++top] = {h - cnt, r};
        v.v2 = 1, v.v5 = -h, modify(1, r, v), v.v2 = v.v5 = 0;
        for (auto [l, i] : qry[r]) res[i] = query(l);
    }

    for (int i = 1; i <= q; i ++) write(res[i]);
}