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

· · 题解

模拟赛 T1。

思路

题目的操作是将一个数字乘二，不难发现，一次对于 x_i 的乘二操作将会影响到从 i 开始的一段区间。假设我们修改 i 之后会影响到 j，那么需要满足 {a_k\times 2 > a_{k + 1}}(\forall i\le k<j)。这提醒我们可以用链表去维护每一段这样的区间，每次当修改后的两个链表一个的末尾乘二大于另一个链表的开头就合并起来。每次操作就用线段树维护一下链表对应的区间的操作次数即可。

但这还不足以让我们做出此题。继续观察性质，发现当我们确定了区间的开头之后从这个位置开始到第 n 个位置的操作次数就已经确定了。因此从大到小扫描线一个 i 处理所有 l=i 的询问的答案。每次加入一个 a_i 根据 a_i 和 a_{i + 1} 的大小关系分类讨论一下即可。具体实现见代码。

代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2.5e5 + 5;

int n, q, a[N], ans[N], lst[N], nxt[N];

struct Node{
    int r, id;
};

struct node{
    int l, r, w, tag;
}tr[N << 2];

vector <Node> pro[N];

#define mid (tr[p].l + tr[p].r >> 1)
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)

void Build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;

    if(l == r) {
        return;
    }

    Build(ls(p), l, mid);
    Build(rs(p), mid + 1, r);
}

__inline__ void Push_Down(int p) {
    if(!tr[p].tag) {
        return;
    }

    tr[ls(p)].w += (tr[ls(p)].r - tr[ls(p)].l + 1) * tr[p].tag;
    tr[rs(p)].w += (tr[rs(p)].r - tr[rs(p)].l + 1) * tr[p].tag;
    tr[ls(p)].tag += tr[p].tag;
    tr[rs(p)].tag += tr[p].tag;
    tr[p].tag = 0;
}

void Push_Date(int p, int l, int r, int k) {
    if(tr[p].l >= l && tr[p].r <= r) {
        tr[p].tag += k;
        tr[p].w += (tr[p].r - tr[p].l + 1) * k;
        return; 
    }

    Push_Down(p);

    if(l > mid) {
        Push_Date(rs(p), l, r, k);
    }
    else if(r <= mid) {
        Push_Date(ls(p), l, r, k);
    }
    else {
        Push_Date(ls(p), l, r, k);
        Push_Date(rs(p), l, r, k);
    }

    tr[p].w = tr[ls(p)].w + tr[rs(p)].w;
}

int Query(int p, int l, int r) {
    if(tr[p].l >= l && tr[p].r <= r) {
        return tr[p].w;
    }

    Push_Down(p);

    int res;

    if(l > mid) {
        res = Query(rs(p), l, r);
    }
    else if(r <= mid) {
        res = Query(ls(p), l, r);
    }
    else {
        res = Query(ls(p), l, r) + Query(rs(p), l, r);
    }

    tr[p].w = tr[ls(p)].w + tr[rs(p)].w;

    return res;
}

signed main(){
//  freopen("increasing.in", "r", stdin);
//  freopen("increasing.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> q;

    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    for(int i = 1; i <= q; i ++) {
        int l, r;
        cin >> l >> r;
        pro[l].push_back({r, i});
    }

    for(int i = 1; i <= n; i ++) {// 初始化链表。
        lst[i] = i - 1;
        nxt[i] = i + 1;
    }

    Build(1, 1, n);

    for(int i = n; i >= 1; i --) {
        if(i != n && a[i] > a[i + 1]) {
            while(a[i] > a[i + 1]) {// 如果后面的数小于当前添加的数，那么需要一直乘二直到大于当前数
                a[i + 1] *= 2;

                if(nxt[i + 1] - 1 != i + 1) {// 链表尾部也乘二方便判断合并
                    a[nxt[i + 1] - 1] *= 2;
                }

                Push_Date(1, i + 1, nxt[i + 1] - 1, 1);// 区间加维护操作数

                if(nxt[i + 1] != n + 1 && a[nxt[i + 1] - 1] * 2 > a[nxt[i + 1]]) {// 如果需要合并区间
                    lst[nxt[nxt[i + 1]]] = i + 1;
                    nxt[i + 1] = nxt[nxt[i + 1]]; 
                }
            }

            lst[nxt[nxt[i]]] = i;
            nxt[i] = nxt[nxt[i]];
        }
        else if(a[i] * 2 > a[i + 1] && i != n) {// 当前值可能需要和后面的链表合并
            lst[nxt[nxt[i]]] = i;
            nxt[i] = nxt[nxt[i]];
        }

        for(auto it : pro[i]) {// 回答询问。
            ans[it.id] = Query(1, i, it.r);
        }
    }

    for(int i = 1; i <= q; i ++) {
        cout << ans[i] << '\n'; 
    }

    return 0;
}