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

Claire0918 · 2025-11-17 15:35:29 · 题解

我们发现左端点一旦变化每个点的修改次数就会完全不同，于是我们考虑枚举左端点，倒着加入每个数同时维护每个点的操作次数，将询问挂在左端点上做区间查询。

我们注意到如果 a_{i + 1} \geq a_i 且 a_{i + 1} < 2a_i，那么这两个就绑定了，换而言之如果对 a_i 操作 x 次，那么也一定要对 a_{i + 1} 操作 x 次。我们考虑将这些被绑定的点缩成一个区间，每次插入一个新的点 i 时，从小到大枚举区间 [l_k, r_k]，如果不用操作就直接更新完了，如果需要操作就有 a_{l_k} < a_{r_{k - 1}}，操作完后显然 a_{l_k} < 2a_{r_{k - 1}}，于是 [l_k, r_k] 和前面一个 [l_{k - 1}, r_{k - 1}] 合并成了一个大区间 [l_{k - 1}, r_k]。我们注意到这样一个区间最多操作一次，而区间端点仅有 n 个，所以操作次数是 \mathcal{O}(n) 的。我们用线段树维护每个位置操作次数，时间复杂度 \mathcal{O}((n + q)\log n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

namespace IO{
    #define SIZ (1 << 18)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
    #define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    template <typename tp>
    void rd(tp &x){
        x = 0;
        int f = 1;
        char c = gc();
        for (;!isdigit(c); c == '-' && (f = -1), c = gc());
        for (;isdigit(c); x = x * 10 + (c ^ 48), c = gc());
        x *= f;
    }
    template <typename tp, typename... Arg>
    inline void rd(tp &x, Arg &...args){
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush(){
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c){
        p3 - obuf == SIZ && (flush(), 1538), *p3++ = c;
    }
    template <typename tp>
    void prt(tp x, char ed = '\n'){
        x < 0 && (pc('-'), x = -x);
        static char stk[40];
        int stkp = 0;
        do{
            stk[stkp] = char(x % 10), x /= 10, ++stkp;
        } while (x);
        while (stkp){
            pc(char(stk[--stkp] + '0'));
        }
        pc(ed);
    }
    #undef gc
    #undef SIZ
}

using namespace IO;

const int maxn = 250000 + 10, maxq = 250000 + 10;

int n, q;
int a[maxn], tag[maxn];
long long res[maxq];
vector<pair<int, int> > qry[maxn];
stack<int> stk;

namespace segtree{
    struct{
        int l, r, tag;
        long long val;
    } tree[maxn << 2];
    inline void build(int index, int l, int r){
        tree[index].l = l, tree[index].r = r;
        if (l == r){
            return;
        }
        const int mid = l + r >> 1;
        build(index << 1, l, mid), build(index << 1 | 1, mid + 1, r);
    }
    inline void _add(int index, long long k){
        tree[index].val += (tree[index].r - tree[index].l + 1) * k, tree[index].tag += k;
    }
    inline void pushdown(int index){
        _add(index << 1, tree[index].tag), _add(index << 1 | 1, tree[index].tag), tree[index].tag = 0;
    }
    inline void add(int index, int l, int r, int k){
        if (l <= tree[index].l && r >= tree[index].r){
            return _add(index, k);
        }
        pushdown(index);
        const int mid = tree[index].l + tree[index].r >> 1;
        l <= mid && (add(index << 1, l, r, k), 1538), r > mid && (add(index << 1 | 1, l, r, k), 1538), tree[index].val = tree[index << 1].val + tree[index << 1 | 1].val;
    }
    inline long long query(int index, int l, int r){
        if (l <= tree[index].l && r >= tree[index].r){
            return tree[index].val;
        }
        pushdown(index);
        const int mid = tree[index].l + tree[index].r >> 1;
        long long res = 0;
        l <= mid && (res += query(index << 1, l, r)), r > mid && (res += query(index << 1 | 1, l, r));
        return res;
    }
}

using namespace segtree;

int main(){
    rd(n, q), build(1, 1, n);
    for (int i = 1; i <= n; i++){
        rd(a[i]);
    }
    for (int i = 1; i <= q; i++){
        int l, r;
        rd(l, r), qry[l].push_back(make_pair(i, r));
    }
    stk.push(n + 1);
    for (int i = n; i; i--){
        int l = i + 1, r = stk.top(), posr = i;
        while (r <= n){
            const long long x = a[l - 1] * (1ll << tag[l - 1]), y = a[l] * (1ll << tag[l]);
            if (x > y){
                const int k = ceil(log2(double(x) / y));
                tag[l] += k, r != l && (tag[r] += k), add(1, l, r, k), stk.pop(), posr = r, l = r + 1, r = stk.top();
            }else{
                break;
            }
        }
        stk.push(posr);
        for (auto x: qry[i]){
            res[x.first] = query(1, i, x.second);
        }
    }
    for (int i = 1; i <= q; i++){
        prt(res[i]);
    }
    flush();

return 0;
}