P3865

asd890123 · 2024-07-25 08:42:56 · 题解

看了半天没看到树状数组的题解，让我大跌眼镜（没人写树状数组的题解吗？）。

思路

树状数组最主要的还是 FindMax 函数，在不支持区间相减的情况下我们要采用一种递归策略，用 \operatorname{ask(x,y)} 来表示区间 [x,y] 的最大值，若 y−\operatorname{lowbit}(y)>x，正常递归即可，返回 \max(tree[y],\operatorname{ask}(x,y-\operatorname{lowbit}(y)))，否则只能暴力递归，返回 \max(a[y],\operatorname{x,y-1}))。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>

inline __attribute((always_inline)) static void read(int &x){

    char c = getchar_unlocked();

    x = 0;
    while (!isdigit(c)) c = getchar_unlocked();
    while (isdigit(c)) x = x * 10 + c - '0',c = getchar_unlocked();

}

inline static void write(const int &x){

    if (x > 9) write(x / 10);
    putchar_unlocked(x % 10 + '0');

}

inline __attribute((always_inline)) static void writeln(const int &x){write(x),putchar_unlocked('\n');}

#define N 100005

int n,m,tree[N],a[N];

inline __attribute((always_inline)) static int lowbit(int x){return x & (-x);}

inline __attribute((always_inline)) static void modify(int x,int y){

    for (;x <= n;x += lowbit(x)) tree[x] = std::max(tree[x],y);

}

inline static int ask(const int &x,const int &y){

    if (y > x){

        if (y - lowbit(y) > x) return std::max(tree[y],ask(x,y - lowbit(y)));
        else return std::max(a[y],ask(x,y - 1));

    }

    return a[x];
}

int main(){

    #ifndef ONLINE_JUDGE
        freopen("P3865.in","r",stdin);
    #endif

    read(n),read(m);
    for (int i = 1;i <= n;i++) read(a[i]),modify(i,a[i]);
    while (m--){

        int l,r;

        read(l),read(r);
        writeln(ask(l,r));

    }

    return 0;
}